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();
}

Download