如何查找字符串中連續字符的交集？

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