この事実は、anagrammatical部分文字列について真実ですか？

Question

私は、文字列のanagrammatical部分文字列の数を見つけるアルゴリズムを書こうとしています。例えば、文字列"abba" 4を有している：

（1）"a"、"a"

（2）"b"、"b"

（3）"ab"、"ba"

（4）"abb"、"bba"

私が最適化するために使用しようとしている事実は、

です文字列が長さk、 のストリングのないanagrammaticalペアを持っていない場合

は、それは長さk + 1

のストリングのないanagrammaticalペアを持っていない、あなたはそれが本当かどうかを確認することができますか？

私のアルゴリズム

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によってオフ）のテストケースにおける実際の結果を得ているので。

Answer 1

それはそうではありません - abcdとcdabは長さ4のアナグラムですが、長さ3のアナグラム部分文字列は見つかりません。具体的には、abcdとcdabの両方を含むため、3つのアナグラム（abc,bcd、cda、dab）が含まれていないため、abcdabは機能しません。