MSTRING - String problem
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#include <string.h>
#define max 10000
int n,m,c[1003][30],f[1003][1003];
char s1[1001],s2[1001];
int min(int a,int b)
{
if(a<b)
return a;
else return b;
}
int main()
{
//freopen("MSTRING.in","r",stdin);
scanf("%s %s",s1,s2);
n = strlen(s1);
m = strlen(s2);
for(int i = 0 ; i<= m+1;i++)
for(int j = 0; j<=26;j++)
c[i][j] = m;
for(int i = m-1;i>=0;i--)
for(int j = 'a';j<='z';j++)
{
if(s2[i] == j)
c[i][j-'a'] = i;
else c[i][j-'a'] = c[i+1][j-'a'];
}
for(int i=0;i<n+1;i++)
for(int j=0;j<m+2;j++) f[i][j]=max;
for(int i = 0;i<n;i++)
{
f[i][m+1] = 0;
f[i][m] = 1;
}
for(int i = n-1;i>=0;i--)
for(int j = m-1;j>=0;j--)
{
f[i][j] = min(f[i+1][j],f[i+1][c[j][s1[i]-'a']+1]+1);
}
printf("%d",f[0][0]);
//getch();
}