Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<string.h>
- int i,j,k,l,c[50][50];
- char x[50],y[50],b[50][50];
- void print(int i,int j)
- {
- if(i==0 || j==0)
- return;
- if(b[i][j]=='*')
- {
- print(i-1,j-1);
- printf("%c",x[i-1]);
- }
- else if(b[i][j]=='^')
- print(i-1,j);
- else
- print(i,j-1);
- }
- void lcs()
- {
- k=strlen(x);
- l=strlen(y);
- for(i=1; i<=k; i++)
- c[i][0]=0;
- for(j=0; j<=l; j++)
- c[0][j]=0;
- for(i=1; i<=k; i++)
- for(j=1; j<=l; j++)
- {
- if(x[i-1]==y[j-1])
- {
- c[i][j]=c[i-1][j-1]+1;
- b[i][j]='*';
- }
- else if(c[i-1][j]>=c[i][j-1])
- {
- c[i][j]=c[i-1][j];
- b[i][j]='^';
- }
- else
- {
- c[i][j]=c[i][j-1];
- b[i][j]='-';
- }
- }
- }
- int main()
- {
- printf("First string:");
- scanf("%s",x);
- printf("Second string:");
- scanf("%s",y);
- printf("The LCS is: ");
- lcs();
- print(k,l);
- printf("\n\n LCS table is\n\n");
- for(i=0;i<=k;i++)
- {
- for(j=0;j<=l;j++)
- {
- printf("%d ",c[i][j]);
- }
- printf("\n");
- }
- printf("\n\n arrow table is \n\n");
- for(i=0;i<=k;i++)
- {
- for(j=0;j<=l;j++)
- {
- printf("%c ",b[i][j]);
- }
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement