How do I find intersections of consecutive characters in strings?

Question

Suppose I had the following strings:

blahFOOblahblah
blahblahBARblah
FIZZblahblahblah

Now, I want to interrogate each of these to discover which of them contain any substring of the following:

FIZZbuzz

Obviously, this string shares the word "FIZZ" in common with #3.

I have already taken a look at this post, which doesn't quite accomplish what I am after since it simply focuses on characters (in any order) rather than substrings.

Hint: It's a triply nested loop, comparing every character in your candidate string with every character in each of the target strings. — Robert Harvey, Jul 21 '14 at 23:20
It also has `F` in common with #1, and `b` in common with all three. Exactly what is the criteria? — p.s.w.g, Jul 21 '14 at 23:20
And what exactly would you expect the result to be for `FIZblahFIZZblah` (`FIZ` is one intersection, `FIZZb` is another) — p.s.w.g, Jul 21 '14 at 23:22
1 character is a substring, but it sounds like you don't want to match single characters. You'll have to specify the minimum and maximum number of characters you want to match. — Igby Largeman, Jul 21 '14 at 23:23
@IgbyLargeman--I would most likely be interested in 3+ characters. — Matt Cashatt, Jul 21 '14 at 23:23

AlexD · Accepted Answer · 2014-07-22T12:19:42.723

Are you looking for something like longest common substring?

There are fast, but quite complicated algorithms which solve the task by building and using suffix trees. They have O(n) time for constant size alphabet, and O(n log(n)) time in the worst case, where n is the maximal length of strings.

Below is a possible C# implementation (from http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring). It is not optimal, but could be sufficient in our case.

public int LongestCommonSubstring(string str1, string str2, out string sequence)
{
    sequence = string.Empty;
    if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
        return 0;

    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 //this block resets the string builder if a different LCS is found
                    {
                        lastSubsBegin = thisSubsBegin;
                        sequenceBuilder.Length = 0; //clear it
                        sequenceBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
                    }
                }
            }
        }
    }
    sequence = sequenceBuilder.ToString();
    return maxlen;
}

@cost, I agree, Not sure this constitutes an answer to a c# question. — crthompson, Jul 21 '14 at 23:25
There is a C# section in the Wikipedia article. Checking it now. . . — Matt Cashatt, Jul 21 '14 at 23:26
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#C.23 — Matt Cashatt, Jul 21 '14 at 23:27
@MatthewPatrickCashatt Yep. I also found this page and than read your comment. Thank you anyway! — AlexD, Jul 21 '14 at 23:44
This works well. I had to set a threshold to 4 characters or greater to get meaningful results. Thanks. — Matt Cashatt, Jul 21 '14 at 23:54

How do I find intersections of consecutive characters in strings?

1 Answers1