How many times each word
The compiler of a frequency dictionary needs to know how many times each word of a list occurs in a text: not as a separate word but as a substring, overlaps included. In “abracadabra”, “abra” occurs twice and “a” five times. The list has thousands of words and the text is long, so searching for each word separately takes too long.
Among the tests are the beginning of Part One of “War and Peace” with the novel's dictionary, the genome of phage λ with all four-letter DNA words, and a text with more than eighty million occurrences.
Input
The first line is the text, 1 to 200,000 characters long; any characters except a line break. The second is the number of words k (1 ≤ k ≤ 20,000). Then k lines, a word in each: a word is non-empty, may contain spaces inside, but does not begin or end with a space. The total length of the words is at most 100,000. Words may repeat.
Output
k lines: for each word in input order, the number of positions in the text where it begins.
Examples
Example 1
ushers 4 he she his hers
1 1 0 1
Example 2
абракадабра 8 а абра бра кад ра дабр абракадабра я
5 2 2 1 2 1 1 0
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Build an Aho–Corasick machine from all the words. In one pass it lists all the occurrences. How many can there be in the worst case?
2Hint 2
Take a text of two hundred thousand letters a and the words a, aa, aaa, …: how many will listing find? About 446 occurrences per position, almost 90 million. You need to count without listing.
3Hint 3
If the machine stands in node v, the words of all nodes on the chain of failure links from v to the root end at this position. Write into every node how many times the machine stood there, and think how to spread these numbers along the chains in one traversal.
4The idea
The number of occurrences of a word ending in node u is how many times the machine stood in nodes whose chain of failure links passes through u. The failure links form a tree rooted at the root of the trie, and the sum needed is the sum over the subtree of u in that tree. It is computed by going through the nodes from deep to shallow and adding each node's number to the number of its failure link.
5Walkthrough
Build the trie and the failure links breadth-first, remembering the order of the traversal: the failure link of any node leads to a node visited earlier. Go through the text and count in the array hits how many times the machine stopped in each node after a letter. Then go through the nodes in reverse traversal order and do hits[fail[u]] += hits[u]: when a node's turn comes, all nodes whose chains pass through it have already given it their numbers. The answer for a word is hits of the node where it ends. Repeated words and words that never occur take care of themselves.
Look at the fourth test: at the beginning of Part One «Пьер» (Pierre) occurs 242 times and «Пьера» (Pierre's) 45, and all 45 occurrences of «Пьера» are among those 242: the substring «Пьер» is inside «Пьера». As a separate word «Пьер» occurs less often, and the article shows how to check that in the section on the machine's traps.
5+Solution
6Complexity
O(n + Σ|wi|) time and O(Σ|wi|) memory: building, one pass over the text and one traversal of the nodes. Listing the occurrences along dictionary links costs O(n + Σ|wi| + z), and in the fifth test z = 89,100,765.
7Common mistakes
- Listing the occurrences. Correct, but on a text of one letter and words of its repeats that is tens of millions of steps, seconds in Python.
- Only the node's own word. If in node v you add only to the words ending exactly at v, nested ones are lost: in ushers the machine stands in the node of she, and he ends here too.
- The wrong order. You cannot add to the failure link in order of node numbers: a node may hand over its number before receiving the numbers from deeper ones. You need the reverse breadth-first order, by decreasing depth.
str.countfor each word. It does not count overlaps and costs O(n) per word: twenty thousand passes over two hundred thousand characters.