1205. Equal-Length Pattern Hits
A log scanner looks for known signatures in a stream. Every string in patterns has the same length m. Count the pairs (start index in text, pattern) such that the pattern appears in text beginning at that index. Overlapping occurrences count, and a pattern listed twice is counted twice.
Return the total as a long. Store the polynomial hash of each pattern in a hash map with its multiplicity, slide a rolling hash of length m over text, and add the multiplicity of each window. Use a double modulus so that false matches are unlikely. If m is larger than text.length the answer is 0.
Here 1 <= text.length <= 2 * 10^5, 1 <= patterns.length <= 10^4, all patterns have the same length between 1 and 1000, the total pattern length is at most 2 * 10^5, and all strings are lowercase. The time is O(n + total pattern length).
Example 1
- Input:
- text = "abababab", patterns = ["ab","ba"]
- Output:
- 7
- Explanation:
ab starts at indices 0, 2, 4 and 6, and ba at 1, 3 and 5, so the total is 4 + 3 = 7.
Example 2
- Input:
- text = "aaaa", patterns = ["aa","aa","ab"]
- Output:
- 6
- Explanation:
aa starts at 0, 1 and 2 and appears twice in patterns, so 3 * 2 = 6 hits; ab never occurs.
Example 3
- Input:
- text = "abc", patterns = ["abcd"]
- Output:
- 0
- Explanation:
The only pattern is longer than text, so nothing can match.
Constraints
1 ≤ text.length ≤ 2 * 105
1 ≤ patterns.length ≤ 104
all patterns have the same length m, 1 ≤ m ≤ 1000
total pattern length is at most 2 * 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + total pattern length)
- Space
- O(patterns)