QBSTR - Xâu con chung dài nhất
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <string.h>
int f[1001][1001];
int max(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
// freopen("QBSTR.in","r",stdin);
char s1[10001],s2[10001];
scanf("%s %s",s1,s2);
int n = strlen(s1),m = strlen(s2);
if(s1[0] == s2[0])
f[0][0]=1;
else f[0][0]=0;
for(int i = 1;i<=m;i++)
{
if(s1[0] == s2[i])
f[0][i]=1 ;
else f[0][i] = f[0][i-1];
}
for(int i = 1;i<=n;i++)
{
if(s1[i] == s2[0])
f[i][0]=1 ;
else f[i][0] = f[i-1][0];
}
for(int i = 1;i<n;i++)
for(int j = 1;j<m;j++)
{
if(s1[i]==s2[j])
f[i][j]=f[i-1][j-1]+1;
else f[i][j] = max(f[i-1][j],f[i][j-1]);
// printf("%d %d %d \n",i,j,f[i][j]);
}
printf("%d",f[n-1][m-1]);
// getch();
}