二分 + 字符串哈希
二分
假设最长公共子串长度为ans,则必然存在长度小于ans的公共子串,不存在长度大于ans的公共子串,将区间分为两个部分。
字符串哈希
判断字符串A,B是否存在长为L的公共子串。
记录A中所有长为L的子串的哈希值,遍历B中所有长为L的子串的哈希值,若哈希值之前出现过,说明A,B存在长为L的公共子串(字符串哈希值与字符串一一对应)
最长公共子串不包含数字
将A或B中的数字替换成特殊字符如‘#’,则A,B的公共子串必然不包含数字。
代码
#include <iostream>
#include <unordered_map>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 2e4 + 10, P = 131;
char s[N];
int n, m;
ULL h[N], p[N];
ULL geth(int l, int r)
{
return h[r] - h[l-1] * p[r - l + 1];
}
bool check(int mid)
{
// 记录s1中所有长为mid的所有字串的哈希值
unordered_map<ULL, bool> mp;
for(int i = 1; i + mid - 1 <= n; i++)
{
mp[geth(i, i + mid - 1)] = true;
}
for(int i = n + 1; i + mid - 1 <= n + m; i++)
{
if(mp.count(geth(i, i + mid - 1))) return true;
}
return false;
}
int main()
{
cin >> s + 1;
n = strlen(s + 1);
cin >> s + n + 1;
m = strlen(s + n + 1);
p[0] = 1;
for(int i = 1; i <= n + m; i++)
{
if(i <= n) {
if(isdigit(s[i])) s[i] = '#';
}
h[i] = h[i - 1] * P + s[i];
p[i] = p[i-1] * P;
}
int l = 0, r = min(n, m);
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}