0

基本的に、問題の解決策を見つけようとしています単語とテキストが与えられた場合、アナグラムの出現を返す必要があります。ただし、そこに投稿されたソリューションの一部を完全に理解できませんでした。そこで、この問題を特定のテキストの順列を見つける問題に変換しようとしました。これが私のアルゴリズム（疑似コード）です。それが正しいかどうかを確認するための洞察と、その複雑さを見つけるための洞察が欲しいです。

int findAnagramOccurencesinText(String input,String find)

//generate a list of all possible permutations of the letters in find and store in a list
// eg/ if find ="dog"  then list =["god","odg","dog","gdo","ogd","dgo"]

int occurances=0;
for String (perm:list)
{
     index=-1;
     while(index<input.length)
      {
          index=input.indexOf(perm,index);
          if(index!=-1)
             occurances++;
          index+=1;

      }
}
return occurances;
}

また、複雑さは O(#inputlength) ですか? この特定のアルゴリズムの複雑さを見つける方法についての洞察（正しい場合）をいただければ幸いです。

編集:これは O(n!) ソリューションであることを理解しています。より効率的にするために、私ができる変更はありますか？(アプローチ全体を破棄し、リンクされた質問で言及されている O(n) アプローチに移行する以外)

4

1 に答える 1

0

O(n!)一連のn要素の順列があります。

したがって、文字列検索アルゴリズムが線形時間であると仮定すると、時間の計算量は次のようになります。

O((findLength)! inputLength)

上記は、 が重複してfindいないことを前提としています。重複していない場合、式は少し複雑になります。

于 2013-11-04T06:18:07.823 に答える