UVa 10679

From Algorithmist
Jump to navigation Jump to search

10679 - I love Strings!!![edit]

Summary[edit]

Given a text string and a set of patterns as input, determine patterns that match the text.

Explanation[edit]

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.

Gotchas[edit]

  • 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.

Input[edit]

1
ushers
4
he
she
his
hers

Output[edit]

y
y
n
y

References[edit]

  1. http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf