1529 - Coincidence
Find a longest common subsequence of two strings.
Input
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
Output
For each case, output k – the length of a longest common subsequence in one line.
Examples
Input
google goodbye
Output
4
Solution C
#include <stdio.h> #include <string.h> #define Max 100 int main () { char stra[Max+1]; char strb[Max+1]; int dp[Max+1][Max+1]; while(gets(stra)) { gets(strb); int lena=strlen(stra); int lenb=strlen(strb); for(int i=0;i<=lenb;i++) dp[0][i]=0; for(int i=0;i<=lena;i++) dp[i][0]=0; for(int i=1;i<=lena;i++) for(int j=1;j<=lenb;j++) { if(stra[i-1]==strb[j-1]) dp[i][j]=dp[i-1][j-1]+1; else { if(dp[i-1][j]<dp[i][j-1]) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i-1][j]; } } //for(int i=0;i<=lena;i++) //{ // for(int j=0;j<=lenb;j++) // printf("%d ",dp[i][j]); // printf("\n"); //} printf("%d\n",dp[lena][lenb]); } }
Solution C++
#include<stdio.h> #include<string.h> int a[101][101]; int LCS(const char *s1,const char *s2) { int m=strlen(s1),n=strlen(s2); int i,j; a[0][0]=0; for(i=1;i<=m;++i) a[i][0]=0; for(i=1;i<=n;++i) a[0][i]=0; for(i=1;i<=m;++i) for(j=1;j<=n;++j) { if(s1[i-1]==s2[j-1]) a[i][j]=a[i-1][j-1]+1; else if(a[i-1][j]>a[i][j-1]) a[i][j]=a[i-1][j]; else a[i][j]=a[i][j-1]; } return a[m][n]; } int main() { char s1[101],s2[101]; while(scanf("%s%s",s1,s2)!=EOF) printf("%d\n",LCS(s1,s2)); return 0; }