最长公共子串

给定两个字符串，求这两个字符串的不包含数字的最长公共子串的长度。

输入格式

共两行，每行一个由小写字母和数字构成的字符串。

输出格式

一个整数，表示给定两个字符串的不包含数字的最长公共子串的长度。

如果不存在满足要求的非空公共子串，则输出 $0$。

数据范围

输入字符串的长度均不超过 $10000$。

输入样例：

ab123abccff
abcfacb123

输出样例：

3

解题思路

　　首先把子串看成子序列，看了样例半天都不知道怎么来的。接着被题目名字误导往dp的方向想，然后看了眼数据范围，发现dp的计算量是${10}^8$级别大概率会TLE（事实上并没有超时，可以参考下面动态规划部分的题解），想去优化发现不会，就不会做了。最后看了眼标签才知道怎么做的。

　　首先容易知道答案具有二段性。假设两个字符串中最大的公共子串长度为$\text{ans}$，那么很明显也必然存在长度不超过$\text{ans}$的公共子串。而不会有长度超过$\text{ans}$的公共子串，否则就与假设矛盾了。因此可以用二分。

　　因为是连续的子串，因此当二分出$\text{mid}$，我们就分别对两个字符串$a$和$b$枚举出所有长度为$\text{mid}$的子串，分别构成了两个集合，同时还要保证这些子串中不能包含数字。然后看一下这两个集合中是否有交集，即$a$和$b$是否有相同的长度为$\text{mid}$的子串。如果直接这样做的话这是一个$O(n^3)$的时间复杂度，其中$O(n^2)$用来枚举出两个集合中要比对的子串，再用$O(n)$来判断这两个子串是否相同。优化的方法是，先枚举出$b$中所有长度为$\text{mid}$的子串，存到哈希表中，然后再枚举$a$中所有长度为$\text{mid}$的子串，看看哈希表中是否存在相同的子串，这样就把时间复杂度降到了$O(n^2)$了。这还不够，因此我们需要用到字符串哈希，把判断两个子串是否相同的计算量降到$O(1)$，这样时间复杂度就变成了$O(n)$了。

　　如何判断子串中是否含有数字呢？很简单，我们对字符串中的数字个数求前缀和，对于区间范围是$[i,j]$的子串，如果$s_j - s_{i-1} = 0$，则表明子串中不存在数字，否则反之。

　　AC代码如下，时间复杂度为$O(n \log{n})$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef unsigned long long ULL;
 5 
 6 const int N = 1e4 + 10, P = 13331;
 7 
 8 int n, m;
 9 char a[N], b[N];
10 int s1[N], s2[N];
11 ULL h1[N], h2[N], p[N];
12 
13 ULL get(ULL *h, int l, int r) {
14     return h[r] - h[l - 1] * p[r - l + 1];
15 }
16 
17 bool check(int mid) {
18     unordered_set<ULL> st;
19     for (int i = mid; i <= m; i++) {    // 把b中长度为mid且不含数字的子串加到哈希表中
20         if (s2[i] - s2[i - mid] == 0) st.insert(get(h2, i - mid + 1, i));
21     }
22     for (int i = mid; i <= n; i++) {
23         // a中长度为mid且不含数字的子串在哈希表中出现，表示存在长度为mid的公共子串
24         if (s1[i] - s1[i - mid] == 0 && st.count(get(h1, i - mid + 1, i))) return true;
25     }
26     return false;
27 }
28 
29 int main() {
30     scanf("%s %s", a + 1, b + 1);
31     n = strlen(a + 1), m = strlen(b + 1);
32     p[0] = 1;
33     for (int i = 1; i <= n || i <= m; i++) {
34         p[i] = p[i - 1] * P;
35     }
36     for (int i = 1; i <= n; i++) {
37         h1[i] = h1[i - 1] * P + a[i];
38         s1[i] = s1[i - 1];
39         if (isdigit(a[i])) s1[i]++;
40     }
41     for (int i = 1; i <= m; i++) {
42         h2[i] = h2[i - 1] * P + b[i];
43         s2[i] = s2[i - 1];
44         if (isdigit(b[i])) s2[i]++;
45     }
46     int l = 0, r = min(n, m);
47     while (l < r) {
48         int mid = l + r + 1 >> 1;
49         if (check(mid)) l = mid;
50         else r = mid - 1;
51     }
52     printf("%d", l);
53     
54     return 0;
55 }

　　再给出个动态规划的解法，其实就是最大连续子串和的二维版。

　　定义状态$f(i,j)$表示$a$中前$i$个位置且以$i$结尾，$b$中前$j$个位置且以$j$结尾的所有公共子串中长度的最大值。根据$a_i$与$b_j$是否相同进行状态转移。如果$a_i = b_j$，那么$f(i,j) = f(i-1,j-1)+1$；否则如果$a_i \ne b_j$，那么很明显$f(i,j) = 0$。

　　其中需要需要把第一维的大小优化到$2$，否则就超内存限制了。根据状态转移方程知道每次更新都取决于第一维的前一个状态，因此只需要开个大小为$2$的数组滚动就好了。

　　AC代码如下，时间复杂度为$O(n \times m)$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e4 + 10;
 5 
 6 char a[N], b[N];
 7 int f[2][N];
 8 
 9 int main() {
10     scanf("%s %s", a + 1, b + 1);
11     int n = strlen(a + 1), m = strlen(b + 1);
12     int ret = 0;
13     for (int i = 1; i <= n; i++) {
14         memset(f[i & 1], 0, sizeof(f[0]));
15         for (int j = 1; j <= m; j++) {
16             if (a[i] == b[j] && !isdigit(a[i])) f[i & 1][j] = f[i - 1 & 1][j - 1] + 1;
17             ret = max(ret, f[i & 1][j]);
18         }
19     }
20     printf("%d", ret);
21     
22     return 0;
23 }

参考资料

　　AcWing 3508. 最长公共子串（春季每日一题2023）：https://www.acwing.com/video/4699/