Abbreviation
Time limit2.5sMemory limit1024 MB
Count the ways to split a query string into pieces, where each piece is a prefix of some dictionary word, with duplicates counted as distinct.
- Level
Hard8 of 10
- Topics
- Dynamic programming, String matching, Trie, String
- Solved
- No attempts yet
Problem
Long ago there was a language called Munraebitese. It had many words, and people formed sentences by arranging those words. For example, with the three words "ryan", "is", and "lion", one could form the sentence "lion is ryan is lion". As sentences grew too long, people began abbreviating each word by its first letter, writing the whole sentence as a single word such as "liril". But as the language gained more words, keeping only the first letter made the original sentence impossible to recover, so people changed the rule to take a substring of one or more letters from the front of each word and concatenate them. For instance, given the sentence "lion is ryan is lion", one could take "lion is ryan is lion" and abbreviate it as "liisryanilio". These unidentified words, thought to be abbreviations of sentences, remain a subject of great interest to archaeologists.
An archaeologist named Jongyeong recently found a Munraebitese dictionary. It lists many words, and among them several may be identical. Such words are actually distinct, but the writing system lacked characters to represent the pronunciation, so they ended up spelled the same. For example, if the dictionary contains the word "aa" twice, then "aa aa" can be interpreted as 2 × 2 = 4 distinct sentences.
Jongyeong decided to interpret a Munraebitese word found at a ruin using this dictionary. Since Jongyeong does not yet know which sentence is more natural or how many letters are typically taken from which word, the only way to interpret the word is to enumerate every possibility. Two ways are different if the sentences they use differ, or if the same sentence is used but some word has a different number of letters taken. For example, in the earlier example, besides the way shown above, there is also a way that takes "lion is is ryan is lion". As another example, if the dictionary contains only "aa" and one wants to interpret "aaa", there are three possibilities: "aa aa aa", "aa aa", and "aa aa".
Find in advance how many possibilities Jongyeong must examine.
Input
The first line gives N (1 ≤ N ≤ 10^6), the number of words in the dictionary Jongyeong found.
The next N lines give the words, one per line. All words consist of lowercase English letters, each word has length between 1 and 300 characters, and the total length of all words is at most 10^6 characters.
The next line gives the word Jongyeong wants to interpret. This word also consists only of lowercase English letters and has length between 1 and 200,000 characters.
Output
Print the number of ways to form the given word, modulo 10^9+7.