Summary

Retrieves the Longest Common Substring (LCS) of two given strings.

The code is based on an implementation found at http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring.

Code (C#)

string str1 = "complexity";
string str2 = "flexibility";

int[,] num = new int[str1.Length, str2.Length];
int maxLen = 0;
int lastSubsBegin = 0;
StringBuilder sequenceBuilder = new StringBuilder();

for (int i = 0; i < str1.Length; i++)
{
    for (int j = 0; j < str2.Length; j++)
    {
        if (str1[i] != str2[j])
            num[i, j] = 0;
        else
        {
            if (i == 0 || j == 0)
                num[i, j] = 1;
            else
                num[i, j] = 1 + num[i - 1, j - 1];

            if (num[i, j] > maxLen)
            {
                maxLen = num[i, j];
                int thisSubsBegin = i - num[i, j] + 1;
                if (lastSubsBegin == thisSubsBegin)
                {
                    // If the current LCS is the same as the last time this block ran
                    sequenceBuilder.Append(str1[i]);
                }
                else
                {
                    // Reset the string builder if a different LCS is found
                    lastSubsBegin = thisSubsBegin;
                    sequenceBuilder.Length = 0;
                    sequenceBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
                }
            }
        }
    }
}

Output.Text = string.Format("The longest common substring of '{0}' and '{1}' is '{2}'.",
    str1, str2, sequenceBuilder.ToString()); 
Input Type: Nothing, Output Type: Plain Text

Download Project File

File: Longest_common_substring.dvp (2.17 KB)

To open this file, DataVoila must be installed on your computer. If this is not yet the case, please click here to download the free demo version.