如何查找字符串中连续字符的交集？

Question

假设我有以下字符串：

1. blahFOOblahblah
2. blahblahBARblah
3. FIZZblahblahblah

现在，我想询问每个这些发现其中都包含以下任何字符串：

FIZZbuzz

显然，该字符串与＃3共享单词“FIZZ”。

我已经看过this post，它不完全符合我的要求，因为它只关注字符（以任意顺序）而不是子字符串。

Answer 1

你在寻找什么类似longest common substring？

有快速但相当复杂的算法，通过构建和使用suffix trees来解决任务。他们有O(n)时间为固定大小的字母表，O(n log(n))时间在最坏的情况下，其中n是字符串的最大长度。

下面是一个可能的C＃实现（从http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring）。这不是最佳的，但在我们的情况下可能就足够了。

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; 
}