Keyword Occurrences
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given a post text and a list of banned words, return how many times each word occurs in the text, in the order of
words. Overlapping occurrences all count ("aa" occurs three times in "aaaa"), and a word listed twice is answered twice.
Examples
| text | words | result |
|---|---|---|
"ababa" | ["aba", "ab", "b", "c"] | [2, 2, 2, 0] |
"aaaa" | ["a", "aa", "aaa", "aaaaa"] | [4, 3, 2, 0] |
"hershe" | ["he", "she", "hers", "her"] | [2, 1, 1, 1] |
Example 1 — "aba" occurs at positions 0 and 2, overlapping.
Example 2 — overlapping occurrences all count; a word longer than the text occurs 0 times.
Example 3 — several words can end at the same position.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(text: string, words: string[]) → int[]
Constraints
-
text.length -
words.length,words[i].length - The total length of all words is at most .
textand everywords[i]consist of lowercase English letters.
Expected complexity
- Time
- O(|text| + sum|words| * 26)
- Space
- O(sum|words| * 26)
Examples
| text | words | Expected |
|---|---|---|
"ababa" | ["aba","ab","b","c"] | [2,2,2,0] |
"aaaa" | ["a","aa","aaa","aaaaa"] | [4,3,2,0] |
"hershe" | ["he","she","hers","her"] | [2,1,1,1] |
Hint
Hint
Build an Aho–Corasick automaton: a trie of all words plus failure links (longest proper suffix that is also in the trie),
computed in BFS order. Scan the text once, following trie edges and falling back along failure links, and add 1 to the node
reached after each character. A visit to v also counts for every node on v's failure chain, so add the visit counts to the
failure parent in reverse BFS order instead of walking the chains. Scanning the text once per word is
and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1140 ms | derived |
| Java 25 | 1356 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |