How to compare a set of strings to find common substrings

Question

I'm trying to create a script that looks through a list of strings files and reports on the sub-strings that are most common between them.

For example:

1. Hello, I am string one. I like apples and oranges. We are all strings here.
2. Hello, I am string two. I like apples and oranges. We are all strings here.
3. Hello, I am string three. I like apples and oranges. We are all strings here.
4. Hello, I am string four. I like apples and oranges. I like to express my individuality.

I'd like the script to tell me what are the common elements between the strings, above a certain threshold (for example, 5 characters).

Ideally I'd be told

• "I like apples and oranges" occurs in all files
• "Hello, I am string" occurs in all files
• "We are all strings here" occurs in three of the files.

If functions exist to do this in technologies I'm familiar with - SQL, Javascript, PHP, Ruby or Bash -I'll be extremely happy...

Many thanks,

Jack

Answer 1

This is a hard problem known as the Longest common subsequence problem.

Here is a Python implementation of the algorithm using dynamic programming: http://www.algorithmist.com/index.php/Longest_Common_Subsequence

I don't think that any standard library (C, Java, PHP, Python, Javascript, Ruby, etc.) comes with such a function. But you may look for implementations here: http://www.google.com/codesearch?q=%22longest+common+subsequence%22