最大连续子串长度

■ 题目描述

给定字符串A、B和正整数V，A的长度与B的长度相等， 请计算A中满足如下条件的最大连续子串的长度：

1. 该连续子串在A和B中的位置和长度均相同。
2. 该连续子串 |A[i] – B[i]| 之和小于等于V。其中 |A[i] – B[i]| 表示两个字母ASCII码之差的绝对值。

输入描述：

• 输入为三行： 第一行为字符串A，仅包含小写字符，1 <= A.length <= 1000。
• 第二行为字符串B，仅包含小写字符，1 <= B.length <= 1000。
• 第三行为正整数V，0 <= V <= 10000。

输出描述：

• 字符串最大连续子串的长度，要求该子串 |A[i] – B[i]| 之和小于等于V。

示例 1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

xxcdefg

cdefghi

5

思路：

我们先计算出最长公共子串，并且保证最长公共子串的\(|A[i] - B[i]| <= N\)

那我们应该如何求最长公共子串呢？

这里我们采用动态规划，那首先要确定的就是「状态」和「选择」。

• 状态： 就是此时所指的字符
• 选择： 就是现在是上面移动还是下面移动

dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符（以其为尾字符）的最长公共子串长度

现在我们确定转移方程：

• 当s1[i] == s2[j]时，很明显我们的 dp[i][j] = dp[i-1][j-1] + 1
• s1[i] != s2[j]时，dp[i][j] = 0
• 判断此时dp[i][j] > maxlen && abs(j - i) <= N

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
int N;
int res;

void LCS(string s1, string s2){
    int m = s1.size(), n = s2.size();
    //dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符（以其为尾字符）的最长公共子串长度
    int dp[m + 1][n+1];
    int maxlen = 0;
    for(int i = 0; i <= m; i++) dp[i][0] = 0;
    for(int i = 0; i <= n; i++) dp[0][i] = 0;

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = 0;
            if(dp[i][j] > maxlen && abs(j - i) <= N){
                maxlen = dp[i][j];
                res = abs(j - i);
            }
        }
    }
}

//先求公共子串
int main(){
    string s1, s2;
    cin >> s1 >> s2;
    cin >> N;
    LCS(s1,s2);
    cout << res << endl;
    return 0;
}