Підрахунок слів#4672
Коли Фалес вирушив на віддалений острів у літню відпустку, йому стало нудно, оскільки острів виявився досить одноманітним. Одного дня він помітив слова чи фрази, написані вздовж доріг. Хоча він не розумів деякі з них, Фалес вирішив вигадати гру.
У цій грі потрібно вибрати слово і підрахувати, скільки разів воно зустрічається в тексті вздовж певної ділянки дороги. Погравши кілька разів, Фалес придумав простий спосіб підрахунку слів і вирішив спробувати себе у складнішій версії. Він намалював карту місцевості, відмітивши всі можливі шляхи від свого поточного місця до різних портів, з яких він міг відплисти додому. Він помітив, що всі шляхи на початку збігаються, але згодом розходяться і більше ніколи не перетинаються, кожен з яких веде до іншого порту. Правила цієї вдосконаленої гри полягають у підрахунку кількості різних входжень обраного слова вздовж різних шляхів. Ваше завдання — написати програму, що це виконує.
У першому рядку задано одне ціле число (2 \leq N \leq 15000) — кількість наступних рядків. Кожен з наступних N-1 рядків описує вузли, що утворюють структуру дерева. Вузол — це стартова точка, а всі інші вузли, пронумеровані від до N-1, є або розгалуженнями, або портами. Кожен із наступних N-1 рядків містить два цілі числа — номери двох вузлів , (0 \leq I, J \leq N-1) та текст довжиною символів (1 \leq L \leq 1000), які задають відрізок дороги від вузла до вузла (де завжди є попередником ) із написом, нанесеним уздовж цієї дороги. До вузла не веде жодної дороги, і з порту не веде жодна дорога. Останній рядок файлу містить слово, яке вигадав Фалес.
У вихідний файл виведіть одне ціле число — кількість різних входжень слова уздовж усіх можливих шляхів. Входження визначається його початковою та кінцевою точками (кінцева точка розташована пізніше за початкову на шляху). Входження слова існує тоді, коли конкатенація всіх послідовних символів від початкової до кінцевої точки (включно) утворює шукане слово. Входження слова вважається різним від іншого, якщо воно має різні початкову і/або кінцеву точку. Усі символи — маленькі латинські літери.
Приклад 1