首先 发现L满足单调性, 可以二分
考虑一个DP
设fi 表示将前i个元素分成若干段最大有多少被匹配的
转移
fi=max
len(i) 表示以i 结尾最长能被匹配到的子串的长度, L是当前二分的值
如何求出以i结尾最长能被匹配的子串长度呢?
一个朴素的方法是对每个位置暴力走, 然后能走多少就是多少, 但复杂度太高
发现走的路程都是重复的, 可以记录一些信息来节省时间.
我们可以从位置1开始暴力匹配, 如果走不下去, 就跳后缀链接再匹配
这样可以充分利用之前的信息, 减少复杂度.
然后观察一下转移方程, 发现状态不能优化, 只能优化转移, 发现一个性质.
i - len(i) \leq i + 1 - len(i + 1) \\i - L < i + 1 - L
发现决策的位置是递增的, 于是我们可以维护f_j - j 的单调递减队列.
总体思路就是对M个串建广义SAM, 然后对每个询问串, 先预处理len(i)
然后二分答案, 用dp check.
总复杂度为O(\sum{|S|} + \sum{|P|\log|P|})
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
char s[N];
int tot, fa[N * 2], ch[N * 2][26], len[N * 2], mx[N * 2], f[N * 2];
pair<int, int> qu[N * 2];
inline int insert(int x, int las)
{
if (ch[las][x] && len[las] + 1 == len[ch[las][x]])
return ch[las][x];
int cur = ++tot;
int p = las;
int clone = 0;
int fl = 0;
len[cur] = len[las] + 1;
while (p && !ch[p][x])
{
ch[p][x] = cur;
p = fa[p];
}
if (p == 0)
fa[cur] = 1;
else
{
int q = ch[p][x];
if (len[p] + 1 == len[q])
fa[cur] = q;
else
{
if (p == las) fl = 1;
clone = ++tot;
len[clone] = len[p] + 1;
fa[clone] = fa[q];
memcpy(ch[clone], ch[q], sizeof(ch[q]));
while (p && ch[p][x] == q)
{
ch[p][x] = clone;
p = fa[p];
}
fa[q] = fa[cur] = clone;
}
}
return fl ? clone : cur;
}
inline bool check(int k, int len)
{
int res = 0;
int l = 1, r = 0;
qu[++r] = make_pair(0, 0);
for (int i = 0; i < k; i++)
f[i] = 0;
for (int i = k; i <= len; i++)
{
while (l <= r && qu[l].second < i - mx[i])
l++;
if (l > r)
f[i] = f[i - 1];
else
f[i] = max(f[i - 1], qu[l].first + i);
int t = i - k + 1;
while (l <= r && qu[l].first <= f[t] - t)
r--;
qu[++r] = make_pair(f[t] - t, t);
res = max(f[i], res);
}
double temp = res;
double t = (double)(len) * 0.9;
if (temp >= t)
return true;
else
return false;
}
signed main()
{
int n, m;
cin >> n >> m;
tot = 1;
for (int i = 1; i <= m; i++)
{
cin >> s + 1;
int len = strlen(s + 1);
int las = 1;
for (int j = 1; j <= len; j++)
las = insert(s[j] - '0', las);
}
for (int i = 1; i <= n; i++)
{
cin >> s + 1;
int leng = strlen(s + 1);
int cur = 1;
int res = 0;
for (int j = 1; j <= leng; j++)
{
int x = s[j] - '0';
while (cur != 1 && !ch[cur][x])
{
cur = fa[cur];
res = len[cur];
}
if (!ch[cur][x])
mx[j] = 0;
else
{
res += 1;
mx[j] = res;
cur = ch[cur][x];
}
}
int l = 0;
int r = leng;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid, leng))
l = mid;
else
r = mid - 1;
}
cout << l << endl;
}
return 0;
}