Longest Common Substring
给你两个字符串，s1 和 s2。子字符串是从字符串中连续截取的一段字母，例如从 clockwork 中截取的 ork。找出 s1 和 s2 中共有的最长子字符串，并返回它的长度。如果两个字符串中没有相同的字母，答案就是 0。
函数
- s1string
- 第一个字符串
- s2string
- 第二个字符串
- 返回值integer
- 两个字符串中都出现的最长连续字母块的长度
约束条件
1 ≤ s1.length ≤ 10001 ≤ s2.length ≤ 1000s1和s2由小写英文字母组成。
示例
- 输入
- s1 = "clockwork"s2 = "workshop"
- 输出
- 4
- 解释
work是clockwork的结尾，也是workshop的开头，因此它是一个长度为 4 的公共子串，而且两个字符串中都没有更长的相同片段。
- 输入
- s1 = "hammer"s2 = "harmed"
- 输出
- 2
- 解释
- 这两个单词中都出现了
ha和me，但没有连续 3 个字母相同的片段。这两个单词都按顺序包含 h、a、m、e，但harmed中的 a 和 m 之间有一个 r。
- 输入
- s1 = "fig"s2 = "plum"
- 输出
- 0
- 解释
- 这两个单词没有共同的字母，因此最长公共子串为空，其长度为 0。
进阶
你能否使用滚动哈希，在约 O(n + m) 的时间内测试是否存在长度为 L 的公共子串，然后对 L 进行二分搜索？
提示
逐个打开提示，每个都会多透露一点。
从每一对起始位置进行比较会重复工作：从
i和j开始的块包含从i+1和j+1开始的块。试着复用其中一个答案来得到另一个答案。针对每一对位置，提出一个范围更小的问题：恰好在
s1[i]和s2[j]处结束的公共连续子串有多长？如果两个字母不同，长度就是 0。如果它们相同，长度就是它们前面两个字母对应答案加 1。用这些长度填充表格
run[i][j]，将第 0 行和第 0 列设为 0，表示空前缀。答案是表格中任意位置的最大值，而不只是最后一个单元格。每个单元格只读取左上方的对角单元格，因此从右向左遍历一行就足够了。
题解
从每一对起始位置扩展匹配，会重复读取相同的字母。不妨看看一个块在哪里结束：以 s1[i] 和 s2[j] 结尾的公共块，比以它们前两个字母结尾的公共块长一个字母；如果这两个字母不同，则该公共块为空。用一个表记录这些长度，就能在 O(n × m) 时间内得到答案。
从每一对起始位置开始扩展
结果正确，但无法在最大的测试中运行完毕
思路
每个公共子串都从 s1 的某个位置 i 和 s2 的某个位置 j 开始。对于每一对位置，都向前遍历，直到字母不再相同，并统计步数；最大的步数就是答案。
重复文本会让遍历变得很长。当两个字符串都是由 a 重复 1000 次组成时，每一对位置都会遍历到较短后缀的末尾：大约需要进行 3.3 × 10^8 次字母比较。从 (i, j) 开始的遍历，会在晚一个字母的位置重复从 (i+1, j+1) 开始的整个遍历。
算法
- 将
best = 0。 - 对于
s1中的每个i和s2中的每个j，将k = 0。 - 当
i+k和j+k都在各自的字符串范围内，且s1[i+k] == s2[j+k]时，将k加 1。 - 将最大的
k保存在best中，并返回它。
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
best = 0
for i in range(n):
for j in range(m):
# Walk forward while the two strings agree
k = 0
while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
k += 1
if k > best:
best = k
return best每对末尾的区块长度表
思路
令 run[i][j] 表示恰好以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串的长度；第 0 行和第 0 列的值为 0。这样的子串必须同时包含两个字符。如果它们不同，就不存在这样的子串，该单元格的值为 0。如果它们相同，这个子串就是这对字符加上两个字符串中都提前一个字符结束的子串：run[i-1][j-1] + 1。每个公共子串都会在某处结束，因此答案就是最大的单元格值，无论它位于哪里。
对于 hammer 和 harmed，两个 h 得到 1，两个 a 将其延长到 2，接着 r 会打断这个子串。hammer 中第二个 m 与 harmed 中的 m 相遇时，前面已经出现了 m 和 r 不匹配的情况，因此它从 1 开始，两个 e 将其增加到 2。没有单元格的值达到 3。
每个单元格只需比较一次：对于两个各有 1000 个字符的字符串，无论文本内容如何，都只需比较约一百万次。
算法
- 将
run初始化为n+1行、m+1列，所有元素均为 0，并设置best = 0。 - 让
i遍历 1..n，并在其中让j遍历 1..m，比较s1[i-1]和s2[j-1]。 - 如果匹配，将
run[i][j] = run[i-1][j-1] + 1，并更新best。 - 如果不匹配，将该单元格保留为 0。
- 返回
best。
def longestCommonSubstring(s1, s2):
n, m = len(s1), len(s2)
# run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
run = [[0] * (m + 1) for _ in range(n + 1)]
best = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s2[j - 1]:
run[i][j] = run[i - 1][j - 1] + 1
if run[i][j] > best:
best = run[i][j]
# a mismatch leaves run[i][j] at 0
return best一行，从右向左更新
思路
每个单元格只读取其左上方的对角单元格。因此，只需一个包含 m+1 个数字的数组 run 就能存储整张表，前提是按从右到左的顺序遍历 j：写入 run[j] 时，run[j-1] 仍保存着 s1 上一个字母对应的值，也就是对角单元格的值。
现在，遇到不匹配时必须显式写入 0，因为该位置仍保存着上一行的数字。时间复杂度仍为 O(n × m)，内存则从大约 10^6 个数字降至 1001 个。
算法
- 创建一个长度为
m+1、元素全为 0 的数组run，并设置best = 0。 - 对于
s1中的每个字母ch，让j从m递减到 1。 - 如果
ch == s2[j-1]，则设置run[j] = run[j-1] + 1，并更新best。 - 否则，将
run[j]设置为 0。 - 返回
best。
def longestCommonSubstring(s1, s2):
m = len(s2)
# run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
run = [0] * (m + 1)
best = 0
for ch in s1:
# Right to left, so run[j-1] still holds the value from the previous letter of s1
for j in range(m, 0, -1):
if ch == s2[j - 1]:
run[j] = run[j - 1] + 1
if run[j] > best:
best = run[j]
else:
run[j] = 0
return best
易错点和边界情况
- 返回最后一个单元格。
run[n][m]只涵盖以两个字符串的最后一个字母结尾的连续块。对于abc和abd，结果是 0；而对于ab，结果是 2。 - 不匹配时复制较大的相邻值。这就是子序列规则，它允许连续块跳过字母：对于
hammer和harmed，结果是 4，而不是 2。 - 从左到右遍历单行。对角线上的值会在读取前被覆盖，因此比较
a和aa时，结果是 2。 - 单行计算时跳过重置。来自
s1前一个字母的长度会保留下来，之后还会继续延长一个并不存在的连续块。 - 暴力搜索时遍历却不检查边界。比较
zzzz和zz时，会读取较短字符串末尾之外的内容。
常见问题3
最长公共子串和最长公共子序列有什么区别？
子字符串是一段连续的字母；子序列保持顺序，但中间可以有间隔。对于 hammer 和 harmed，最长公共子字符串的长度为 2，最长公共子序列的长度为 4（hame）。在表格中，字符不匹配时，子字符串对应的单元格会重置为 0，而子序列对应的单元格会复制较大的相邻值。
最长公共子串的时间复杂度是多少？
动态规划解法需要 O(n × m) 时间，使用单行时需要 O(m) 内存。从每一对起始位置进行扩展，最坏情况下需要 O(n × m × min(n, m)) 时间。后缀自动机的时间复杂度约为 O(n + m)，但程序会长得多。
如何返回最长公共子字符串本身？
每当某个单元格的值大于 best 时，也记录这个块在 s1 中结束的位置 i。最后，子字符串就是 s1 中以该位置结尾的 best 个字母。使用严格的大于比较，可以保留在 s1 中找到的第一个最长块。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestCommonSubstring(s1, s2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s1 = "clockwork" s2 = "workshop"
预期输出
4