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

Download