title: Find super-string in a set of strings
body: <p>I have a list of strings, like:</p>
  
  <pre><code>cargo
  cargo pants
  cargo pants men buy
  cargo pants men
  cargo pants men melbourne buy
  </code></pre>
  
  <p>In this, the string that contains all remaining strings is <code>cargo pants men melbourne buy</code>. I'd like to remove all the shorter strings and preserve only the longest "super string".</p>
  
  <p>Note, if 2 queries <code>cargo pants</code> and <code>cargo shorts</code> exist, they will be treated as 2 different queries and won't be combined.</p>
  
  <p>So far, I've been doing this the brute force way - pick a string from set and walk through the same set deleting all other strings that are "substrings" of the current string. Roughly,</p>
  
  <pre><code>for (String p: big_set) {
      for (String q: big_set) {
          if (!p.equals(q)) {
              if (has_all_words(p, q)) { /* If all words in 'p' is also in 'q' */
                  big_set.remove(p);
                  break;
              }
          }
      }
  }
  </code></pre>
  
  <p>Is there an intelligent algorithm to do this in less than O(n^2) time? In this function, <code>has_all_words</code> will preserve the order of words while comparing.</p>
  
  <p>For the curious, I have a massive list of a few billion search queries (like the ones send to Google/Yahoo/Bing) and I'm trying to find hypernyms for these queries. There's a server that parses this string and produces various interesting categories. I am trying to compress the queries list in the hopes of minimizing compute cost and bandwidth. This method surely reduces bandwidth significantly (because humans can't just think of <code>buy cargo pants melbourne</code> in one go), but the pre-computation cost is prohibitive. And so I've been hunting for algorithms that can do this, but I haven't come across anything that does this yet.</p>