带权重的最大公共子串（Maximum Weighted Common Substring）

题目描述
给定两个字符串 s1 和 s2，长度分别为 n 和 m。每个字符在字母表中有一个权重，用数组 weight[char] 表示（char 是小写字母，权重可以是任意整数，包括负数）。你需要找到 s1 和 s2 的一个公共子串（连续的一段），使得这个公共子串的所有字符的权重之和最大。输出这个最大的权重和。

例如：
s1 = "abca", s2 = "abda", 权重：a=2, b=3, c=-1, d=4
最长公共子串是 "ab"，权重和为 2+3=5。但考虑权重，"a" 单独作为子串权重为 2，"b" 为 3，"d" 在 s2 中但 s1 中没有，"ab" 权重 5 是最大。注意 "b" 权重 3 小于 "ab" 的 5。
实际上，s2 中的 "bd" 在 s1 中没有完全匹配。最终最大权重公共子串是 "ab"，权重和 5。

注意：子串必须是连续的，并且必须在两个字符串中都完全一致地出现（字符相同且连续）。这与标准最长公共子串问题类似，但现在目标是最大化权重和而非长度。

解题过程

1. 问题分析
这是“最长公共子串”问题的变种。标准最长公共子串用动态规划定义 dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的公共子串长度。
这里我们需要存储以 s1[i-1] 和 s2[j-1] 结尾的公共子串的最大权重和，而不是长度。
但注意：一个公共子串的权重和是这个子串每个字符权重的累加。如果子串长度>1，那么它的权重和等于其更短前缀的权重和加上当前字符的权重。
因此我们可以利用类似最长公共子串的 DP 递推，但累加权重而不是长度。

2. 状态定义
定义 dp[i][j]：以 s1 的第 i 个字符（下标 i-1）和 s2 的第 j 个字符（下标 j-1）结尾的公共子串的权重和。
注意：如果 s1[i-1] != s2[j-1]，那么它们不能作为公共子串的结尾，dp[i][j] = 0。
如果 s1[i-1] == s2[j-1]，则它们可以扩展前面的公共子串。

3. 状态转移

• 如果 s1[i-1] == s2[j-1]，则当前字符可以接在 dp[i-1][j-1] 表示的公共子串后面，形成更长的公共子串。此时：

  dp[i][j] = dp[i-1][j-1] + weight[s1[i-1]]
  

  这里 weight[s1[i-1]] 是当前字符的权重。
  注意，如果 dp[i-1][j-1] 是 0，表示前面没有公共子串，那么当前就从这个字符开始一个新的公共子串，权重就是 weight[s1[i-1]]，这其实与上面公式一致，因为 dp[i-1][j-1] 为 0 时加当前字符权重即可。

• 如果 s1[i-1] != s2[j-1]，则 dp[i][j] = 0。

4. 初始化

• dp[0][j] = 0 对任意 j，表示 s1 空串与 s2 的任何字符结尾的公共子串不存在，权重和为 0。
• dp[i][0] = 0 对任意 i，同理。
  这样我们 i, j 从 1 开始遍历即可。

5. 获取答案
我们要求的是所有公共子串中权重和的最大值，不一定要以哪个字符结尾。
所以答案为：
ans = max(dp[i][j]) 对所有 i=1..n, j=1..m 取最大值。
注意：这个最大值可能是负数（如果所有权重都是负的，那么最大权重子串可能是单个负权重字符，但有可能空子串权重 0 更大？但题目中“公共子串”通常认为非空，如果允许空子串权重 0，则需与 0 比较，但一般约定子串非空，所以这里直接取 dp 中的最大值，如果全负，答案就是负的）。

6. 举例验证
例：s1="abca", s2="abda", weight: a=2, b=3, c=-1, d=4。
计算 dp 表（尺寸 5x5，索引 0 行/列为 0）：

i=1, j=1: s1[0]='a', s2[0]='a' 相同，dp[1][1]=dp[0][0]+weight('a')=0+2=2
i=1, j=2: s1[0]='a', s2[1]='b' 不同，dp[1][2]=0
i=1, j=3: 'a' vs 'd' 不同，0
i=1, j=4: 'a' vs 'a' 相同，dp[1][4]=dp[0][3]+2=0+2=2

i=2, j=1: 'b' vs 'a' 不同，0
i=2, j=2: 'b' vs 'b' 相同，dp[2][2]=dp[1][1]+3=2+3=5
i=2, j=3: 'b' vs 'd' 不同，0
i=2, j=4: 'b' vs 'a' 不同，0

i=3, j=1: 'c' vs 'a' 不同，0
i=3, j=2: 'c' vs 'b' 不同，0
i=3, j=3: 'c' vs 'd' 不同，0
i=3, j=4: 'c' vs 'a' 不同，0

i=4, j=1: 'a' vs 'a' 相同，dp[4][1]=dp[3][0]+2=0+2=2
i=4, j=2: 'a' vs 'b' 不同，0
i=4, j=3: 'a' vs 'd' 不同，0
i=4, j=4: 'a' vs 'a' 相同，dp[4][4]=dp[3][3]+2=0+2=2

dp 中最大值是 dp[2][2]=5，对应子串 "ab"（s1[0..1] 与 s2[0..1]），权重 2+3=5，正确。

7. 优化空间
注意到 dp[i][j] 只依赖于 dp[i-1][j-1]，因此可以用滚动数组优化到 O(m) 空间。
用一维数组 dp 长度 m+1，同时保留一个变量 prev 记录左上角的值（即 dp[i-1][j-1]）。
遍历 i=1..n，每次对 j 从 1..m 遍历，用 temp 保存当前未更新的 dp[j] 作为下一轮的 prev。

伪代码：

max_weight = -inf
dp[0..m] = 0
for i = 1 to n:
    prev = 0
    for j = 1 to m:
        temp = dp[j]
        if s1[i-1] == s2[j-1]:
            dp[j] = prev + weight[s1[i-1]]
            max_weight = max(max_weight, dp[j])
        else:
            dp[j] = 0
        prev = temp

注意每次遇到字符不同时，dp[j] 设为 0，因为不能以它们结尾。
最后输出 max_weight。

8. 边界与特殊情况

• 如果两个字符串没有公共字符，dp 全 0，答案 0？但 dp 全 0 表示没有非空公共子串，但 0 是 dp 值，最大是 0，但空子串是否允许？通常公共子串要非空，如果全不同字符，则没有非空公共子串，但按我们的 dp 定义，最大值 0 是初始值，这不对应任何子串。题目可能要求非空，所以如果 max_weight 是 0 且没有实际匹配，需注意，但一般情况下如果有匹配，dp 至少有一个正或负值。更稳妥：用一个布尔标记是否有过匹配，如果全不匹配，答案就是 0 还是负无穷？根据题意，如果完全没有公共子串，最大权重和可以认为是 0（空串），但空串通常不算子串。这里我们先按非空处理，所以如果 max_weight 初始化负无穷，最后如果还是负无穷，则说明无公共子串，可以返回 0 或负无穷依题目而定。但常见是如果无公共子串，权重和为 0（没有字符）。

• 权重可能为负，所以最大权重和可能是负数（比如所有权重为负，公共子串只能取某个负权重字符）。

9. 复杂度

• 时间复杂度 O(n*m)
• 空间复杂度 O(min(n,m)) 用滚动数组

10. 扩展思考

• 如果权重全为 1，则退化为最长公共子串长度。
• 可以扩展为允许一次不匹配或带通配符的变种，类似带权重的带 k 次不匹配的最长公共子串。
• 也可以求具体子串内容，记录 dp 更新时的起始位置。

这道题的核心是将最长公共子串的长度累加改为权重累加，递推时仍然是连续匹配的传递。