Count Pattern Occurrences
mediumStrings II+20 XPTime limit 2s
A plagiarism checker needs to know how many times a pattern appears inside a long text. Count all occurrences, including overlapping ones: aa appears 3 times in aaaa, and aba appears twice in ababa.
Input:
- line 1: the text
- line 2: the pattern
Both contain only lowercase letters.
Output: the number of positions where the pattern occurs in the text.
Constraints: 1 ≤ pattern length ≤ text length ≤ 10⁵. Comparing the pattern at every position can take 10¹⁰ steps on texts like aaaa…a — too slow.
Think about it: KMP. Compute the prefix function of pattern + '#' + text: pi[i] is the length of the longest proper prefix of the string that also ends at position i. Every position in the text part where pi[i] equals the pattern length is the end of one occurrence. The whole thing is O(n + m).
Sample input 1
aaaa aa
Sample output 1
3
Sample input 2
ababa aba
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).