CareerCup

concatenate the original string
back to back
and then find the rotated string as a substring
if it exists you are done.

int circular(char* str1, char* str2)
{
char* tmp1=NULL;
char*tmp2 =NULL;
int size1=0;
int size2 = 0;

tmp1=str1;
while(*tmp1!='\0')
{
tmp1++;
size1++;
}

tmp1=str2;
while(*tmp1!='\0')
{
tmp1++;
size2++;
}

if(size1!=size2)
return 0;

tmp2=str2;
tmp1=str1;
while(*tmp2 != *str1 && *tmp2!='\0')
tmp2++;
if(*tmp2=='\0')
return 0;

while(size1)
{
if(*tmp2=='\0')
tmp2=str2;
else if(*tmp2==*tmp1 )
{
tmp2++;
tmp1++;
size1--;

}
else
return 0;
}

return 1;

}

<pre lang="c" line="1" title="CodeMonkey93165" class="run-this">#include<stdio.h>
#include<string.h>
int main()
{
char a[50],b[50];
int res;
gets(a);
gets(b);
res=isperm(a,b);
if(res==1)
printf("\nYeah it is");
else
printf("\nNo it is nt ");
return 0;
}
int isperm(char a[], char b[])
{
char c[50];
int l1,l2,i,j,k,s;
l1=strlen(a);
l2=strlen(b);
if(l1!=l2)
return(9);
for(i=0;i<l1;i++)
{
j=i+1;
k=0;
while(k<l1)
{
c[k]=a[j];
k++;
j=(j+1)%l1;
}
s=strcmp(c,b);
if(s==0)
return 1;
}
return(9);
}
</pre><pre title="CodeMonkey93165" input="yes">abcd
bcda</pre>

better use KMP algorithm here for finding substring

We can use a circular queue , dequeue a element and enqueue the same element in to the queue , if we do the same for n times we can generate all the circular permutations of the given string.

can't we just check if the first letter of the first string appears in the second string .. if it does then compare the succeeding letters in both strings using modulo arithmetic for the second string.. i guess it should be O(n) ... please correct me if i'm wrong.

#include <iostream>
#include <string.h>
using namespace std;
bool iscircular(const char* input1, const char* input2)
{
int len1 = strlen(input1);
int len2 = strlen(input2);
char* temp = new char[len1+len2+1];
strcpy(temp,input1);
strcat(temp,input2);
char* p = strstr(temp,input2);
cout<<*p<<endl;
if(p!=NULL)
return 1;
else
return 0;
}
int main()
{
char input1[] = "abcd";
char input2[] = "cdab";
bool result = iscircular(input1, input2);
return 1;
}

I wrote a version without using any strlen or strcmp. I think I am covering all the cases, but please let me know if there is any input that breaks it

bool isCircularPermutation(char str1[], char str2[])
{
int xstr1 =0;
int xstr2= 0;
int idxfound = -1;
while (str2[xstr2])
{
if (idxfound == -1 && str1[0] == str2[xstr2])
{
idxfound = xstr2;
}
if (idxfound != -1)
{
if (str1[xstr1++] != str2[xstr2])
{
idxfound = -1;
xstr1 = 0;
}
}
xstr2++;
}
if (idxfound != 1)
{
for (xstr2 = 0; xstr2<idxfound; xstr2++)
{
if (str1[xstr1] == '\0' || str1[xstr1] != str2[xstr2])
{
return false;
}
xstr1++;
}
}
else
{
return false;
}
if (str1[xstr1] != '\0')
{
return false;
}

return true;
}

1. Create a suffix tree and a trie from the first word.
2. See whether both have same length.
3. Match the second word with the suffix tree as much as we can.
4. If the remaining second word is in prefix tree then it is circular
Eg:
cdab
cd will match one of the suffixes. The remaining is ab which will be in prefix tree. Hence it is cyclic.
So this we can do in O(n)

#include <iostream>
#include <string>

using namespace std;

int main(){
    string s1 = "abcdaad";
    string s2 = "cdabaaad";
    
    string conc = s1 + s1;
    cout << conc << endl;
    if ( s1.length() == s2.length() && conc.find(s2) !=  string::npos )
       cout << s1 << " and " << s2 << " are circular anagrams" << endl;
    else
        cout << " not circular anagrams";
    
 cin.get();
 return 0;
    
}

#include <stdio.h>

int main()
{
char str1[20], str2[20];
int i, x, y, comp;

printf("Enter The String str1: ");
gets(str1);

printf("Enter The String str2: ");
gets(str2);

x = strlen(str1);
y = strlen(str2);

if(x != y)
{
printf("strings are different!!\n");
}
else
{
for(i=1; i<x; i++)
{
comp = strcmp(str1, str2, x);

if(comp == 0)
{
printf("strings are same!!\n");
exit(0);
}
else
{
left_shift_string(str2);
}
}

printf("strings are different!!\n");
}
}

left_shift_string(char *ptr)
{
char start, *temp;

start = *ptr;
temp = ptr;

while(*ptr != '\0')
{
*ptr = *(ptr+1);
ptr++;
}
ptr--;
*ptr = start;

printf("shifted string = %s\n", temp);
}