I have 1,000,000 strings with different lengths(the largest length is limited), I want to find all sub stirngs. Is there a good algorithm？ for example,
- s1:abcd
- s2:bcd
- s3:cd
- s4:bcde
substrings are:
- s2 in s1
- s2 in s4
- s3 in s2
- s3 in s4
Asked
Active
Viewed 55 times
0
-
If i am not mistaken you mean s2 in s1+s2 and so on right? – Zzap Feb 07 '17 at 08:56
-
1Just a thought: Use a Trie (prefix tree) structure. After adding all strings, you should be able to get your substring list by mere traversal. – Sirko Feb 07 '17 at 08:58
-
I mean s2 is in s1 and s4 – 郭志良 Feb 07 '17 at 08:59
-
1There are O(n^2) results. You don't want them all. – n. m. could be an AI Feb 07 '17 at 09:03
-
how to reduce comparation count when sub strings have no common prefix? – 郭志良 Feb 07 '17 at 10:01
-
1You may want to take a look at: http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english – zeppelin Feb 07 '17 at 13:58