最长公共子串

动态规划

说明

只在相邻字符相同的状态上延长连续匹配；与可跳过字符的子序列不同。

分析

子串要求连续，因此只有当前两个末尾字符相同时，才能从左上方状态加一；失配时长度直接归零。逐行保存状态即可把空间降到 O(m)。

图解推演

xabcd 与 yabcz 的公共连续片段是 abc，长度 3。状态表示“以当前两字符结尾”的长度：a 对 a 得 1，b 对 b 得 2，c 对 c 得 3，d 对 z 必须清零。答案是所有状态的最大值，不一定在最后一格；这是与公共子序列的关键区别。

查看图表代码

适用前提与边界

示例按字节比较，处理 Unicode 字符时可先转成 rune 切片。

示例输入与调用

fmt.Println(LongestCommonSubstring("xabcd", "yabcz"))

运行输出

3

完整 Go 示例

package main

import "fmt"

func LongestCommonSubstring(a, b string) int {
	prev := make([]int, len(b)+1)
	best := 0
	for i := 1; i <= len(a); i++ {
		next := make([]int, len(b)+1)
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				next[j] = prev[j-1] + 1
				best = max(best, next[j])
			}
		}
		prev = next
	}
	return best
}

func main() {
	fmt.Println(LongestCommonSubstring("xabcd", "yabcz"))
}