Search code examples
stringgrepsubstringtext-comparison

How to compare a set of strings to find common substrings

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

Solution

  • 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