1085. Many Patterns at Once
A moderation team keeps a list of banned phrases and scans a long chat log for them. The log is a lowercase string text and the phrases are the strings in patterns. For every phrase you must report how often it appears in the log.
Return an array ans with ans[i] equal to the number of start indices where patterns[i] occurs inside text. Occurrences may overlap, and a phrase that is a piece of another phrase is counted on its own. The list may contain the same phrase several times; each entry gets its own (equal) answer.
Checking each phrase separately against the whole log is too slow when there are thousands of phrases, so the whole list should be handled in one pass over the text.
Example 1
- Input:
- text = "abababa", patterns = ["aba","ab","ba","c"]
- Output:
- [3,3,3,0]
- Explanation:
"aba" starts at 0, 2 and 4, "ab" at 0, 2 and 4, "ba" at 1, 3 and 5, and "c" never appears.
Example 2
- Input:
- text = "aaaa"patterns = ["a","aa","aaa","aaaa","aaaaa"]
- Output:
- [4,3,2,1,0]
- Explanation:
A run of four letters contains 4, 3, 2 and 1 overlapping copies of the first four patterns and none of the fifth, which is longer than the text.
Example 3
- Input:
- text = "banana"patterns = ["ana","nan","an","banana","na"]
- Output:
- [2,1,2,1,2]
- Explanation:
"ana" overlaps itself at positions 1 and 3, "nan" occurs once, "an" and "na" twice each, and the whole word once.
Constraints
1 ≤ text.length ≤ 105
1 ≤ patterns.length ≤ 2000, each pattern is non-empty and the total length of all patterns is at most 40000
All strings consist of lowercase English letters
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 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n + L * 26)
- Space
- O(L * 26)