问题描述

解题分析

程序实现

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1000;
char s1[MAXN];
char s2[MAXN];
int maxLen[MAXN][MAXN];

int main()
{
    memset(s1, 0, sizeof(s1));
    memset(s2, 0, sizeof(s2));
    memset(maxLen, 0, sizeof(maxLen));
    while(cin >> s1 >> s2)
        {
            int s1_len = strlen(s1);
            int s2_len = strlen(s2);
            for(int i = 1; i <= s1_len; i++)
                for(int j = 1; j <= s2_len; j++)
                    if(s1[i-1] == s2[j-1])
                        maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
                    else
                        maxLen[i][j] = max(maxLen[i - 1][j], maxLen[i][j - 1]);
            cout << maxLen[s1_len][s2_len]<<endl;
        }
    return 0;
}

运行结果