[CTSC2012]熟悉的文章（后缀自动机单调队列）

/*

首先答案显然是具有单调性的， 所以可以二分进行判断

然后当我们二分过后考虑dp来求最长匹配个数， 发现每个点能够转移的地点 肯定是一段区间， 然后这样就能够得到一个log^2算法

至于每个点的匹配最长区间， 我们可以预处理出所有地点的最长匹配串

然后发现这个东西可以进行单调栈优化， 原因是往后能往前最大匹配到的点是不会超过前面的， 否则前面那个也会更长

然后就能快乐地一个log了

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 2800010

#define mmp make_pair

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

char s[M];

int ch[M][2], cnt = 1, lst = 1, fa[M], len[M], n, m;

void insert(int c) {

	int p = ++cnt, f = lst;

	lst = p;

	len[p] = len[f] + 1;

	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];

	if(f == 0) {

		fa[p] = 1;

	} else {

		int q = ch[f][c];

		if(len[q] == len[f] + 1) {

			fa[p] = q;

		} else {

			int nq = ++cnt;

			memcpy(ch[nq], ch[q], sizeof(ch[q]));

			fa[nq] = fa[q];

			len[nq] = len[f] + 1;

			fa[p] = fa[q] = nq;

			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];

		}

	}

}

int q[M], h, t, pre[M], f[M];

bool check(int k) {

	int l = strlen(s + 1);

	h = 1, t = 0;

	for(int i = 1; i <= l; i++) {

		f[i] = f[i - 1];

		if(i < k) continue;

		while(h <= t && f[q[t]] - q[t] <= f[i - k] - i + k) t--;

		q[++t] = i - k;

		while(h <= t && q[h] < i - pre[i]) h++;

		if(h <= t) f[i] = max(f[i], f[q[h]] + i - q[h]);

	}

	return f[l] * 10 >= l * 9;

}

void getpre() {

	int up = strlen(s + 1), now =  1, lenn = 0;

	for(int i = 1; i <= up; i++) {

		int c = s[i] - '0';

		while(now && !ch[now][c]) now = fa[now], lenn = len[now];

		if(!now) now = 1, lenn = 0;

		else now = ch[now][c], lenn++;

		pre[i] = lenn;

	}

}

int work() {

	getpre();

	int l = 1, r = strlen(s + 1);

	while(l + 1 < r) {

		int mid = (l + r) >> 1;

		if(check(mid)) l = mid;

		else r = mid;

	}

	if(!check(l)) return -1;

	if(check(r)) return r;

	return l;

}

int main() {

	n = read(), m = read();

	for(int i = 1; i <= m; i++) {

		lst = 1;

		scanf("%s", s + 1);

		int l = strlen(s + 1);

		for(int j = 1; j <= l; j++) insert(s[j] - '0');

	}

	while(n--) {

		scanf("%s", s + 1);

		cout << work() << "\n";

	}

	return 0;

}

巴特西

[CTSC2012]熟悉的文章（后缀自动机单调队列）

最新文章

热门文章

巴特西

[CTSC2012]熟悉的文章 （后缀自动机 单调队列）

最新文章

热门文章

[CTSC2012]熟悉的文章（后缀自动机单调队列）