Contents

1. 1. 题目：

题目：

　　先输入str1, str2两个字符串，然后输入询问次数q，问：str1从i开始到结尾，和str2
从j开始到结尾的最长公共子序列的长度，并打印出来

• 定义状态：s[i][j]代表字符串[i , n-1]和[j , n-1]前缀相同的最大个数
• 状态转移方程：s[i][j] = str[i] == str[j] ? s[i+1][j+1] + 1 : 0;

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#define MAXN 1000
using namespace std;

char str1[MAXN], str2[MAXN];
int dp[MAXN][MAXN];

int main(){

    int i, j, q;
    scanf("%s%s", str1, str2);
    memset(dp, 0, sizeof(dp));  //边界处理
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for(i = len1 - 1; i >= 0; i--){ 
        for(j = len2; j >= 0; j--){
            dp[i][j] = str1[i] == str2[j] ? dp[i+1][j+1] + 1 : 0;
        }
    }
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &i, &j);
        printf("%d\n", dp[i][j]);//输出最长公共子序列的长度
        for(int start = i; start < i + dp[i][j]; start++)//输出从i，j开始的最长公共子序列
            printf("%c", str1[start]);
        printf("\n");
    }
    return 0;
}