title: Efficient Data Structure For Substring Search?
body: <p>Assume I have a set of strings S and a query string q.  I want to know if any member of S is a substring of q.  (For the purpose of this question substring includes equality, e.g. "foo" is a substring of "foo".)  For example assume the function that does what I want is called <code>anySubstring</code>:</p>
  
  <pre><code>S = ["foo", "baz"]
  q = "foobar"
  assert anySubstring(S, q)  # "foo" is a substring of "foobar"
  
  S = ["waldo", "baz"]
  assert not anySubstring(S, q)
  </code></pre>
  
  <p>Is there any easy-to-implement algorithm to do this with time complexity sublinear in <code>len(S)</code>?  It's ok if S has to be processed into some clever data structure first because I will be querying each S with a lot of q strings, so the amortized cost of this preprocessing might be reasonable.</p>
  
  <p>EDIT:  To clarify, I don't care <strong>which</strong> member of S is a substring of q, only whether at least one is.  In other words, I <strong>only</strong> care about a boolean answer. </p>