Word Count#4672
When Thales traveled to a remote island for his summer vacation, he found himself in need of entertainment, as the island was rather uneventful. One day, he noticed words or phrases written along the roads. Although he couldn't understand some of them, he decided to create a game.
In this game, you choose a word and count how many times it appears in the text along a specific segment of the road. After playing this game a few times, Thales devised a simple way to count the words and decided to try himself in a more challenging version. He drew a map of the area, marking all possible paths from his current location to the various ports from which he could sail home. He observed that while all paths might start the same, they eventually diverge and never intersect again, each leading to a different port. The rules of this advanced game involve counting the number of distinct occurrences of a chosen word along different paths. Your task is to write a program that accomplishes this.
The first line contains an integer (2 \leq N \leq 15000)—the number of subsequent lines. Each of the next N-1 lines describes the nodes, which form a tree structure. Node is the starting point, and all other nodes, numbered from to N-1, represent either forks or ports. Each of the next N-1 lines contains two integers representing two nodes , (0 \leq I, J \leq N-1) and text of length characters (1 \leq L \leq 1000), which define the road segment from node to node (where is always a predecessor of ) with text along the road segment. There is no road leading to node , and no road exits from a port. The last line of the file contains the word Thales thought of.
The output file should contain a single integer—the number of distinct occurrences of the word along all possible paths. An occurrence is defined by its starting and ending points (the ending point occurs later on the path than the starting point). An occurrence exists when the concatenation of all consecutive characters from the starting to the ending point (inclusive) forms the desired word. An occurrence of the word is considered distinct from another if it has a different starting and/or ending point. All characters are lowercase Latin letters.
Example 1