1843. Many Words, One Text
A text t is given, then q words. For each word, print how many times it occurs
in t.
Occurrences may OVERLAP, and counts are wanted, one per word.
``` t = mississippi issi -> 2 at 1 and at 4, sharing three characters ss -> 2 xyz -> 0
t = aaaa a -> 4 aa -> 3 aaaa -> 1 ```
A counter that skips past each match reports 2 for aa in aaaa instead of 3,
which was confirmed by running it.
## What most people try first
Search the text separately for each word. Even at O(|t| + |word|) per search
with the prefix function of problem 1802, the total is O(q |t|), which at
q = 20000 and |t| = 200000 is 4 * 10^9. When the words are short, the text
is scanned again and again for no reason. The method below reads the text ONCE
and then spends only O(|word| log |t|) per word, about 3.4 * 10^6 in total.
## Every occurrence is a suffix beginning with the word
A word w occurs at position i exactly when the suffix starting at i begins
with w. Sorted order groups those suffixes together, because anything sorting
between two suffixes that both start with w also starts with w.
So build the suffix array once, then for each word find the block of suffixes beginning with it, by two binary searches:
lo = the first sorted position whose suffix is not smaller than w
hi = the first sorted position whose suffix is larger than w, ignoring anything after |w| characters
count = hi - lo
Both searches compare the word against the first |w| characters of a suffix,
which costs O(|w|), so each word costs O(|w| log |t|).
## The comparison that makes both searches work
Compare the word with a suffix character by character, for at most |w|
characters:
compare(suffix at p, w):
for x in 0 .. |w|-1:
if p + x is past the end of t: return SMALLER
if t[p+x] != w[x]: return t[p+x] < w[x] ? SMALLER : LARGER
return EQUAL
The first search wants the first position that is not SMALLER; the second wants
the first that is LARGER. Because the comparison stops at |w| characters and
calls a long suffix with the right prefix EQUAL, the two searches bracket
exactly the suffixes beginning with w.
Treating a suffix shorter than w as SMALLER is what puts it below the block
rather than inside it.
## Cost
O(|t| log^2 |t|) once, then O(|w| log |t|) per word, so about 6.5 * 10^7
plus 3.4 * 10^6 at the limits.
Constraints - `1 ≤ length of t ≤ 200000` - `1 ≤ q ≤ 20000` - `1 ≤ length of each word ≤ 200000` - the total length of all the words is at most `200000` - a word may be longer than the text, in which case its count is 0
Input
The first line contains the text t.
The second line contains the integer q.
Each of the next q lines contains one word. The text and the words are lowercase English letters.
Output
Print one integer on its own line for each word, in the order the words arrive: how many times that word occurs in the text, counting overlapping occurrences.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.