trouver que deux chaînes sont

Question

comment trouver que deux chaînes sont cycliques ou non, en moins de O (n^2) et sans utiliser un troisième tableau.
entrée
str1 = "ABCDE" str = "eabcd"
sortie
cyclique
entrée
str1 = "cabdc" str = "ccabd"
sortie
cyclique
entrée
str1 = "ddabnhdd" str = "dddabnhd"
sortie
cyclique

S'il vous plaît me suggérer la meilleure solution possible ???

Answer 1

Vous devez faire une recherche de chaîne optimisée, il y en a qui prennent O(n) + O(m), vous pouvez les trouver here. Après cela, il suffit de doubler la première chaîne et de rechercher la seconde, cela prendra O(n) fois.
Pour éviter d'utiliser un troisième tableau, faites simplement tout accès à la première chaîne modulo n.

Answer 2

La réponse devrait être: minimal-cyclic-shift

Le coût algorithme O (n) et aucun tableau supplémentaire du tout, et il trouve le décalage cyclique minimal de mot.

à l'aide, nous pouvons facilement vérifier:

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: Je ne pense pas que toute solution qui comprend une chaîne de recherche partie répondra à l'exigence: sans utiliser une troisième rangée dans O (n). Alors peut-être que la solution à décalage cyclique minimal est la seule.