soj2796lcs.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>
#include<string.h>

int s[201][201];

int LCS(char *s1,char *s2)
{
    int row=strlen(s1);
    int col=strlen(s2);
    int i,j;
    for(i=0;i<=row;i++)
    {
        s[i][0]=0;
    }
    for(i=1;i<=col;i++)
    {
        s[0][i]=0;
    }
    for(i=1;i<=row;i++)
    {
        for(j=1;j<=col;j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                s[i][j]=s[i-1][j-1]+1;
            }
            else
            {
                if(s[i-1][j]>=s[i][j-1])
                {
                    s[i][j]=s[i-1][j];
                }
                else
                    s[i][j]=s[i][j-1];
            }
        }
    }
    return s[row][col];
}

int main(void)
{
    char s1[201],s2[201];
    while(scanf("%s%s",s1,s2)==2)
    {
        printf("%d\n",LCS(s1,s2));
    }
    return 0;
}