c++ - 发现两个字符串是循环的

Question

如何在小于O(n^2) 且不使用第三个数组的情况下找到两个字符串是否循环。
输入
str1 = "abcde" str="eabcd"
输出
循环
输入
str1 = "cabdc" str="ccabd"
输出
循环
输入
str1 = "ddabnhdd" str="dddabnhd"
输出
循环

请建议我最好的解决方案？？？

Answer 1

你需要做一个优化的字符串搜索，有需要的，你可以在这里O(n) + O(m)找到它们。 之后只需将第一个字符串加倍并在其中搜索第二个字符串，这将需要一些时间。 为避免使用第三个数组，只需每次访问第一个字符串以 n 为模。
O(n)

Answer 2

The answer should be : minimal-cyclic-shift

The algorithm costs O(n) time and no additional array at all, and it finds the minimal cyclic shift of word.

using that, we can easily check :

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: I don't think any solution that includes a searching string part will meet the requirement : without using a third array in O(n). So maybe the minimal-cyclic-shift solution is the only one.