c++ - 2 つの文字列が循環していることを確認する

Question

O（n ^ 2）未満で、3番目の配列を使用せず に、2つの文字列が循環しているかどうかを確認する方法。
入力
str1 = "abcde" str="eabcd"
出力
サイクリック
入力
str1 = "cabdc" str="ccabd"
出力
サイクリック
入力
str1 = "ddabnhdd" str="dddabnhd"
出力
サイクリック

考えられる最善の解決策を教えてください???

Answer 1

最適化された文字列検索を行う必要がありO(n) + O(m)ます。 その後、最初の文字列を 2 倍にして 2 番目の文字列を検索すると、時間がかかります。 3 番目の配列の使用を避けるには、最初の文字列へのすべてのアクセスをモジュロ n にします。
O(n)

Answer 2

答えは次のとおりです。

このアルゴリズムは O(n) 時間かかり、追加の配列はまったくなく、単語の最小の循環シフトを見つけます。

それを使用して、簡単に確認できます。

int a=minLexCyc(str1),b=minLexCyc(str2),i,n=strlen(str1);
for(i=0;i<n;i++){
        if(str1[(a+i)%n]!=str2[(b+i)%n]){
                cout<< "not cyclic";
                return ;
        }
}
cout<< "cyclic";

PS:検索文字列部分を含むソリューションは、 O(n)で3番目の配列を使用せずに要件を満たすとは思いません。したがって、おそらく最小サイクリック シフト ソリューションが唯一のソリューションです。