這是關於一個字母子串的事實嗎？

我想寫一個算法，找到一個字符串的字母子串的數量。例如，該串"abba"具有4：這是關於一個字母子串的事實嗎？

（1）"a"，"a"

（2）"b"，"b"

（3）"ab"，"ba"

（4）"abb"，"bba"

我試圖用來優化的一個事實是

如果字符串沒有anagrammatical對長度爲k的子串，那麼它就沒有anagrammatical對長度爲k + 1

的子串，你可以確認這是否是真還是假？

因爲我的算法

static int NumAnagrammaticalPairs(string str) 
{ 
    int count = 0; // count of anagrammatical pairs found 
    int n = str.Length/2; // OPTIMIZATION: only need to look through the substrings of half the size or less 
    for(int k = 1; k <= n; ++k) 
    { 
     // get all substrings of length k 
     var subsk = GetSubstrings(str,k).ToList(); 

     // count the number of anagrammatical pairs 
     var indices = Enumerable.Range(0, subsk.Count); 
     int anapairs = (from i in indices 
         from j in indices 
         where i < j && IsAnagrammaticalPair(subsk[i], subsk[j]) 
         select 1).Count(); 

     // OPTIMIZATION: if didn't find any anagrammatical pairs in the substrings of length k, 
     // there are no anagrammatical pairs in the substrings of length k+1, so we can exit 
     // the loop early 
     if(anapairs == 0) 
      break; 
     else 
      count += anapairs; 
    } 
    return count;  
}

越來越結果sliggggtttthhhhly斷開（通常關閉的1）中的測試例的實際效果。

來源

2016-08-09 Ms. Corlib

爲什麼你停在一半的字符串的大小？你的第四個例子（「abb」和「bba」）在長度爲4的字符串中顯示長度爲3的對，因爲你的算法停止查看長度爲2的字符串。 – juharr

情況並非如此 - abcd和cdab是長度爲4的字符串，但找不到長度爲3的字符串子字符串。具體而言，abcdab將不起作用，因爲它包含abcd和cdab，但不包含3個字符（來自abc,bcd，cda,dab）。

來源

2016-08-09 16:39:08

這是關於一個字母子串的事實嗎？

回答

相關問題