Take the 2-minute tour ×

I have N strings. I'm looking to find all substrings that are at least 2 character long that occur in at least 2 strings.

For the following strings:

  1. my name is daniel
  2. what is your name?
  3. they call me daniel

It should return (excluding strings with only one character):

  • " name" – 1. & 2.
  • " is" – 1. & 2.
  • " daniel" – 1. & 3.
  • " me" – 1. & 3.
  • " y" – 1. & 3.

The length of the strings could be really long (1KB-10KB). I have almost no memory issues (~2GB) - I just need to calculate those common strings as quickly as possible.

Thanks in advance! Daniel.

share|improve this question
And have you begun any kind of research into this? Made a start at all? –  David Thomas Sep 24 '12 at 9:39
Of course!. Most algorithms find LCS (longest-common-substrings) between 2 strings. That means I'll have to run them 2^N times (all combinations) which is not very efficient. Other algorithms find LCSs that appear in all strings - they find the shortest string and just go over each char and check whether it appears in the next string - if so, check the next one and so on. then continue checking to find the longest LCS. Because of the way these algorithms are built (find the shortest string first), I can't change them to find strings in just some of them. –  Avenger Sep 24 '12 at 9:42
add comment

2 Answers

I suggest make 3 tables in a database:

  1. a index table holding single words from the text
  2. a table that holds the text
  3. a table that hold a reference from a word to a text

The approach would be something like this:

  1. Add the string to the text table(2)
  2. Split the string in words
  3. for every word: if the word is not in the index (1) table add it.
  4. for every word: Add a entry in the reference table(3), linking to the word and the text table

If you have this structure you now very easy can count cerain words, how often they occur, and where they occur.

If you put indexes on the index table on the words, you can search very fast.

share|improve this answer
How do you define words? "atestb" and "ksdstesta" have "test" in common between them. I'm not trying to find common words, I'm trying to find common substrings. sorry if the example was a bit confusing. –  Avenger Sep 24 '12 at 9:47
add comment

I've found out that my best option is to make all possible combinations between the strings (roughly n^2 combinations) and then run a LCS algorithm on each combination. now I can compare all the results process them.

It's O(n^2*m^2) - n^2 combinations of O(m^2) for each run of the LCS algorithm.

I know it's the naive implementation, but its the best one I could find.

Thanks anyway :-)

share|improve this answer
add comment

Your Answer


