最長(zhǎng)公共字串問(wèn)題，經(jīng)典的DP模型。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1458
#include <stdio.h>
#include <string.h>

int dp[250][250];
char s[250];
char t[250];

int lcs ( char s1[], char s2[] )
{

    int len1 = strlen ( s1 );
    int len2 = strlen ( s2 );
    int i, j;

    for ( i=0; i<=len1; i++ )
    {
        for ( j=0; j<=len2; j++ )
        {
            if ( i==0 || j==0 )
            {
                dp[i][j] = 0;
            }
            else
            {
                if ( s1[i-1] == s2[j-1] )
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = dp[i][j-1] >dp[i-1][j] ? dp[i][j-1] : dp[i-1][j]; 
                }
            }
        }
    }
    return dp[i-1][j-1];
}
int main()
{
    while (scanf("%s%s", &s, &t) != EOF)
    {
        printf("%d\n", lcs(s, t));
    }
    return 0;
}