W3W (What 3 Words)
Time limit1sMemory limit512 MB
Count how many distinct ordered triples of words (repetition allowed) can be joined with dots to form a code whose dot-stripped version equals the queried string S.
- Level
Hard8 of 10
- Topics
- String, Trie, Dynamic programming, String matching
- Solved
- No attempts yet
Problem
While watching TV, Sehun happened to learn about the W3W system.
W3W (What 3 Words) is a geocoding system that divides every location on Earth into 3m × 3m cells and assigns each cell a unique code made of 3 words and their arrangement order.
For example, the main gate entrance of Ajou University's Paldal Hall is expressed by the three words 환율, 비법, 달콤한.
Sehun prepared a word list consisting of N words. From this list, he picks 3 words with repetition allowed, puts . between the picked words, and joins them in order to make a unique string. Call this a unique code. Since the word list contains no duplicate words, N3 unique codes can be made in total.
It would be nice if users searched with the words properly separated by ., but Sehun wants search to work well even when they do not.
Output the number of unique codes in the search results when the user searches with the . characters removed.
Input
The first line gives N, the number of words in the word list. (1 ≤ N ≤ 100,000)
The next N lines give the words in the list, one per line. All words in the list are distinct, and the total length of the words does not exceed 1,000,000.
The N + 2-th line gives the string S that the user searched for. (3 ≤ |S| ≤ 3,000,000)
All words and strings consist of lowercase English letters.
Output
Output the number of unique codes in the search results.