title: Python: optimal search for substring in list of strings
body: <p>I have a particular problem where I want to search for many substrings in a list of many strings. The following is the gist of what I am trying to do:</p>
  
  <pre><code>listStrings = [ACDE, CDDE, BPLL, ... ]
  
  listSubstrings = [ACD, BPI, KLJ, ...]
  </code></pre>
  
  <p>The above entries are just examples. len(listStrings) is ~ 60,000, len(listSubstrings) is ~50,000-300,000, and len(listStrings[i]) is anywhere from 10 to 30,000.</p>
  
  <p>My current Python attempt is:</p>
  
  <pre><code>for i in listSubstrings:
     for j in listStrings:
         if i in j:
            w.write(i+j)
  </code></pre>
  
  <p>Or something along these lines. While this works for my task, it's horribly slow, using one core and taking on the order of 40 minutes to complete the task. Is there a way to speed this up?</p>
  
  <p>I don't believe that I can make a dict out of listStrings:listSubstrings because there is the possibility of duplicate entries which need to be stored on both ends (although I may try this if I can find a way to append a unique tag to each one, since dicts are so much faster). Similarly, I don't think I can pre-compute possible substrings. I don't even know if searching dict keys is faster than searching a list (since <code>dict.get()</code> is going to give the specific input and not look for sub-inputs). Is searching lists in memory just that slow relatively speaking?</p>