Funcia
Lv.4aho-corasickstringtrie

Keyword Occurrences

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

textwordsresult
"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

  • 1≤1 \le text.length ≤500,000\le 500{,}000
  • 1≤1 \le words.length ≤50,000\le 50{,}000, 1≤1 \le words[i].length
  • The total length of all words is at most 500,000500{,}000.
  • text and every words[i] consist of lowercase English letters.

Expected complexity

Time
O(|text| + sum|words| * 26)
Space
O(sum|words| * 26)

Examples

textwordsExpected
"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 O(K⋅∣text∣)O(K \cdot |text|) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131140 msderived
Java 251356 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.