最长公共子串之DP解法

缘起

突然发现这么经典的问题我的博客里面竟然没有, 但是这种问题的DP解法几乎是没有什么用的. 因为它的复杂度达到了O(n^2). 但是还是需要知道的.

分析

最长公共子串和最长公共子序列都称为 LCS， 但是和【1】不同, 最长公共子串和最长公共子序列唯一的区别就在于前者需要连续, 而后者不需要. 本文后面的LCS都指的是最长公共子串.

LCS 问题的解法有2种

  1. 朴素的DP ， O(n^2)
  2. 后缀数组, 但是本蒟蒻还不会~ 呜呜呜, 后面一定学会，再也不水题了~

本文将第1种解法固定下来. 虽然它只能处理 1000数量级的字符串.

下面的dp[i][j] 表示s[i]=t[j]（当然, 如果相等的话） 开始的LCS的长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "stdafx.h"
#include <string.h>
#include <stdio.h>
#define LOCAL

char s[1005], t[1005];
int dp[1005][1005],m,n,ans;

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%s%s", s,t))
	{
		m = strlen(s), n = strlen(t);
		memset(dp, 0, sizeof(dp));
		ans = 0;
		for (int i = m-1; ~i; i--)
		{
			for (int j =n-1; ~j; j--)
			{
				if (s[i]==t[j])
				{
					dp[i][j] = dp[i+1][j+1]+1; // 则s[i]=t[j]可以续上dp[i+1][j+1]这一段儿, 所以+1
					if (dp[i][j]>ans)
					{
						ans = dp[i][j]; // 自然, 这里还可以维护一下LCS的起始位置
					}
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

测试数据

1
2
3
4
5
6
7
8
9
10
hpavoc
mavens
hpavoc
mavenocs
hpaoc
mavens
答案
2
2
1

参考

【1】https://yfsyfs.github.io/2019/07/28/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97%EF%BC%88LCS%EF%BC%89%E9%97%AE%E9%A2%98-hdu-1243-%E5%8F%8D%E6%81%90%E8%AE%AD%E7%BB%83%E8%90%A5/#more