10679 - I love Strings!!!
Given a text string and a set of patterns as input, determine patterns that match the text.
This problem is almost exactly stated as the Aho Corasick algorithm. The Aho Corasick algorithm constructs an augmented trie so that all patterns can be matched in a single scan of the text. See the reference below for quality reference notes.
- Patterns may be repeated
- Make sure you handle the case of input text as all X, and the patterns as all X of varying sizes with reasonable speed.
1 ushers 4 he she his hers
y y n y