1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 5000;
char A[maxn];
char B[maxn];
int dp[maxn][maxn][2]={0};
int flag[maxn][maxn]={0};
const int idx = 2500;
int main()
{
    while (NULL != gets(A+idx) && NULL != gets(B+idx))
    //while (EOF != scanf("%s%s", A+idx, B+idx))
    {
        int la=strlen(A+idx) + idx - 1;
        int lb=strlen(B+idx) + idx - 1;
        for(int i = idx; i <= la; ++ i)
        {
            for (int j = idx; j <= lb; ++ j)
            {
                if (A[i] == B[j])
                    flag[i][j] = flag[i-1][j-1] + 1;
                else
                    flag[i][j] = 0;
                dp[i][j][0] = max(dp[i][j-1][0], dp[i-1][j][0]);
                dp[i][j][0] = max(dp[i-1][j-1][0], dp[i][j][0]);
                dp[i][j][0] = max(dp[i][j-1][1], dp[i][j][0]);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX