String Algorithms (KMP, Z, Rolling Hash, Trie)
You are given a text and a pattern, both non-empty strings of lowercase letters. Count how many times the pattern occurs in the text. Occurrences may overlap. The pattern may be longer than the text, in which case the answer is 0.
The first line is the text. The second line is the pattern.
Print one integer: the number of occurrences.
1 <= |text|, |pattern| <= 1000000 Only lowercase letters a to z.
1000 ms256 MB
aaaaa aa
4
The pattern starts at positions 0, 1, 2 and 3.
abcabcabd abcabd
1
It occurs once, starting at position 3.
