带权重与惩罚的最优近似公共子串C++动态规划算法实现求助

问题核心说明 #

首先明确：你要解决的是连续近似公共子串问题，和普通最长公共子序列（LCS，不要求连续）逻辑不同，和经典最长公共子串的DP状态定义逻辑一致，仅转移规则增加了权重和错配惩罚，核心思路类似局部序列比对的Smith-Waterman算法。

动态规划设计 #

状态定义 #

设两个输入字符串为s1（长度n）、s2（长度m）：

• dp[i][j]：以s1第i位、s2第j位为结尾的近似公共子串可获得的最高得分
• 额外用变量max_score记录全局最高得分，后续通过回溯即可提取对应子串

转移规则 #

权重数组w[26]存储每个英文字母的权重，p为单字符错配惩罚：

// 字符串下标从0开始，dp数组下标从1开始规避边界判断
如果 s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + w[s1[i-1] - 'A']
否则:
    dp[i][j] = dp[i-1][j-1] - p
// 若当前得分小于0，说明从当前位置重新开启子串得分更高，截断负收益前缀
dp[i][j] = max(dp[i][j], 0)

每次计算完dp[i][j]后，若其值大于max_score，就更新max_score和对应结束位置。

完整C++实现 #

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string findBestApproxSubstring(string s1, string s2, vector<int>& weight, int mismatch_penalty) {
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    int max_score = 0;
    int end_s1 = 0, end_s2 = 0; // 最优子串在两个字符串中的结束下标

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + weight[s1[i-1] - 'A'];
            } else {
                dp[i][j] = dp[i-1][j-1] - mismatch_penalty;
            }
            dp[i][j] = max(dp[i][j], 0);
            // 仅当得分更高时更新，保证得分相同时先出现的子串被保留
            if (dp[i][j] > max_score) {
                max_score = dp[i][j];
                end_s1 = i - 1;
                end_s2 = j - 1;
            }
        }
    }

    if (max_score == 0) return ""; // 无有效公共子串
    // 回溯计算子串长度
    int len = 0;
    int i = end_s1 + 1, j = end_s2 + 1;
    while (i > 0 && j > 0 && dp[i][j] > 0) {
        len++;
        i--;
        j--;
    }
    return s1.substr(end_s1 - len + 1, len);
}

int main() {
    string s1 = "AABCC", s2 = "AADCC";
    int p = 3;
    // 测试用例1：A权重1、C权重2
    vector<int> w1(26, 1);
    w1['C' - 'A'] = 2;
    cout << "测试用例1结果：" << findBestApproxSubstring(s1, s2, w1, p) << endl; // 输出CC
    // 测试用例2：所有字母权重为1
    vector<int> w2(26, 1);
    cout << "测试用例2结果：" << findBestApproxSubstring(s1, s2, w2, p) << endl; // 输出AA
    return 0;
}

优化说明 #

如果输入字符串长度较大，可对空间做优化：由于每个dp[i][j]仅依赖左上角的dp[i-1][j-1]，可将二维DP数组压缩为一维数组，空间复杂度从O(nm)降低到O(min(n,m))，时间复杂度保持O(nm)不变。

内容的提问来源于stack exchange，提问作者ACE