Its quite long... but its simple...
pls tell me its worst case time complexity..!!!
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
int check(char *p,int n)// this function checks for pallindromicity of
the string passed.
{
char a[100],b[100];
int k;
for(k=0;k<=n;k++)
b[k]=(p[k]);
b[k]=NULL;
for(k=0;k<=n;k++)
a[k]=(b[n-k]);
a[k]=NULL;
k=strcmp(a,b);
printf("\n%s %s,%d",b,a,k);
return k;
}
main()
{
char str[100];
scanf("%s",&str);
int N,cuts=0,i=0,j,r,index,pall[10],k=0;
N=strlen(str);
while(i<N)
{ printf("\nHere");
for(j=N-1;j>i;)
{
if(str[i]==str[j])
{
if((r=check((&str[i]),(j-i)))==0)
{ if(j==N-1)
{ cuts=-1; j=N;
printf("Cuts=0");.//string itself is pallindrome
getch(); exit(0);
}
else{
cuts++;
pall[k]=i;
pall[k+1]=j;
i=j+1;
j=N-1;
k+=2; continue;}
}
}
j--;
}
i++;
}
if(cuts==0)
printf("\nMinimum cuts=%d",N-1);
else
{
for(i=0;i<k;i++)
printf("\n%d",pall[i]);
cuts+=(pall[0]-0);
for(i=0;i<k;i+=2)
cuts+=(pall[i+2]-pall[i+1]);
cuts+=(N-pall[k]-2);
printf("\n Cuts=%d",cuts);
}
getch();
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
