One solution is below : can u pls tell me its complexity....is it less
than O(n^2)..?
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
int check(char *p,int n)
{
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])
{ printf("\n%d %d",i,j);
if((r=check((&str[i]),(j-i)))==0)
{
if(j==N-1)
{
cuts=-1;
j=N;
printf("Cuts=0");
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;
}
Its quite long... but its simple...
pls tell me its worst case time complexity..
On 8/4/11, ankit sambyal <[email protected]> wrote:
> thnks amit..
>
> --
> 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.
>
>
--
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.
