Return string that is not a substring of other strings - is it possible in time less than O(n^2)?
<p>You are given an array of strings. you have to return only those strings that are not sub strings of other strings in the array.
Input - <code>['abc','abcd','ab','def','efgd']</code>.
Output should be - <code>'abcd'</code> and <code>'efgd'</code>
I have come up with a solution in python that has time complexity O(n^2).
Is there a possible solution that gives a lesser time complexity?
My solution:</p>

<pre><code>def sub(l,s):
  l1=l
  for i in range (len(l)):
        l1[i]=''.join(sorted(l1[i]))
  for i in l1:      
         if s in i:
              return True
  return False

def main(l):
      for i in range(len(l)):
            if sub(l[0:i-1]+l[i+1:],l[i])==False:
                  print l[i]


main(['abc','abcd','ab','def','efgd'])                  
</code></pre>

<p>Using <a href="https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm" rel="nofollow">Aho-Corasick</a> should allow you to get asymptotic run time of <code>O(n)</code>, at the expense of adding additional memory usage, and higher fixed multiplier on costs (ignored by big-O notation, but still meaningful). The complexity of the algorithm is the sum of several components, but none of them multiply, so it should be linear by all metrics (number of strings, length of strings, longest string, etc.).</p>

<p>Using <a href="https://pypi.python.org/pypi/pyahocorasick" rel="nofollow"><code>pyahocorasick</code></a>, you'd do an initial pass to make an automaton that can scan for all of the strings at once:</p>

<pre><code>import ahocorasick

# This code assumes no duplicates in mystrings (which would make them mutually
# substrings). Easy to handle if needed, but simpler to avoid for demonstration

mystrings = ['abc','abcd','ab','def','efgd']

# Build Aho-Corasick automaton, involves O(n) (in combined length of mystrings) work
# Allows us to do single pass scans of a string for all strings in mystrings
# at once
aut = ahocorasick.Automaton()
for s in mystrings:
    # mapping string to itself means we're informed directly of which substring
    # we hit as we scan
    aut.add_word(s, s)
aut.make_automaton()

# Initially, assume all strings are non-substrings
nonsubstrings = set(mystrings)

# Scan each of mystrings for substrings from other mystrings
# This only involves a single pass of each s in mystrings thanks to Aho-Corasick,
# so it's only O(n+m) work, where n is again combined length of mystrings, and
# m is the number of substrings found during the search
for s in mystrings:
    for _, substr in aut.iter(s):
        if substr != s:
           nonsubstrings.discard(substr)

# A slightly more optimized version of the above loop, but admittedly less readable:
# from operator import itemgetter
# getsubstr = itemgetter(1)
# for s in mystrings:
#     nonsubstrings.difference_update(filter(s.__ne__, map(getsubstr, aut.iter(s))))

for nonsub in nonsubstrings:
    print(nonsub)
</code></pre>

<p>Note: Annoyingly, I'm on a machine without a compiler right now, so I can't install <code>pyahocorasick</code> to test this code, but I've used it before, and I believe this should work, modulo stupid typos.</p>

python string python-2.7 substring