求公共子字符串的最大长度问题,当然是DP了。


题目:飞机票直达(C - Common Subsequence


代码:

Memory: 5716 KB
Time: 46 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000+10;
int dp[maxn][maxn], len1, len2, i, j;
char str1[maxn], str2[maxn];
int main()
{
    while(~scanf("%s %s", &str1, &str2))
    {
        len1=strlen(str1);
        len2=strlen(str2);
        for(i=0;i<maxn;i++)dp[0][i]=dp[i][0]=0; //初始化边界为0
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
        {
            if(str1[i-1]==str2[j-1])dp[i][j]=dp[i-1][j-1]+1;   //如果当前两个字符相同则公共字符串可以加1
            else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
        }
        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}