学步园

http://poj.org/problem?id=1458  模版题  

code1:

#include <stdio.h>
#include <string.h>
#define MAXN 301
int LCS[MAXN][MAXN];
char str1[MAXN], str2[MAXN];

int main()
{
    int len1, len2, i, j;
    while(scanf("%s%s",str1,str2)!=EOF)
    {
        memset(LCS,0,sizeof(LCS));
        len1 = strlen(str1);
        len2 = strlen(str2);
        for(i=1; i<=len1; ++i)
        for(j=1; j<=len2; ++j)
        {
            if(str1[i-1]==str2[j-1])
                LCS[i][j] = LCS[i-1][j-1]+1;
            else
            {
                if(LCS[i-1][j]>LCS[i][j-1])
                    LCS[i][j] = LCS[i-1][j];
                else
                    LCS[i][j] = LCS[i][j-1];
            }
        }
        printf("%d\n",LCS[len1][len2]);
    }
    return 0;
}

code2(滚动数组):

#include <stdio.h>
#include <string.h>
#define MAXN 301
int LCS[2][MAXN];
char str1[MAXN], str2[MAXN];

int main()
{
    int len1, len2, i, j,k1,k2;
    while(scanf("%s%s",str1,str2)!=EOF)
    {
        memset(LCS,0,sizeof(LCS));
        len1 = strlen(str1);
        len2 = strlen(str2);
        for(i=1; i<=len1; ++i)
        for(j=1; j<=len2; ++j)
        {
            k1 = i &1;
            k2 = (i+1) &1;
            if(str1[i-1]==str2[j-1])
                LCS[k1][j] = LCS[k2][j-1]+1;
            else
            {
                if(LCS[k2][j]>LCS[k1][j-1])
                    LCS[k1][j] = LCS[k2][j];
                else
                    LCS[k1][j] = LCS[k1][j-1];
            }
        }
        printf("%d\n",LCS[len1 &1][len2]);
    }
    return 0;
}