P4595 [COCI2011-2012#5] POPLOCAVANJE

P4595 [COCI2011-2012#5] POPLOCAVANJE
第一反应AC自动机，好家伙，竟然只有 62.5MB 空间。那么我直接放弃没想法。那咱们先不考虑时间。
第一重优化时间：发现要匹配也就匹配最长的串，所以在fail树上记一下fail能跳到的最长串。
发现每个串的询问其实互相独立，所以考虑可以分块建AC自动机，然后直接分块做完了。

/*
	Name:
	Author: Gensokyo_Alice
	Date:
	Description:
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef int ll;
const ll MAXN = 1e6+10;

ll N, M, tot, tag[MAXN], tim, vis[MAXN], head[MAXN], cnt = -1, maxn[MAXN], ans[MAXN], sum;
char ss[MAXN], st[MAXN];

struct nod {
	ll fail, cnt, nt[26];
} t[MAXN];

struct edge {
	ll nt, to;
} E[MAXN];

void ins(char*, ll);
void bfs();
void cha();
void add(ll, ll);
void dfs(ll); 
void clear(ll);

int main() {
	memset(head, -1, sizeof(head)); 
	scanf("%d", &N);
	scanf("%s", ss+1);
	scanf("%d", &M);
	ll SIZ = sqrt(M);
	for (ll i = 1; i <= M; i += SIZ) {
		tot = 0;
		for (ll j = i; j < i + SIZ && j <= M; j++) {
			scanf("%s", st+1);
			ins(st, strlen(st+1));
		}
		bfs();cha(); tim++;
		clear(0); tag[0] = tim;
	}
	for (ll i = 1; i <= N; i++) ans[i] += ans[i-1], sum += (ans[i] == 0);
	printf("%d\n", sum);
    return 0;
}

void cha() {
	ll now = 0;
	for (ll i = 1; i <= N; i++) {
		now = t[now].nt[ss[i]-'a'];
		ans[i+1] -= 1, ans[i-maxn[now]+1] += 1;
	}
}

void ins(char* tem, ll len) {
	ll now = 0;
	for (ll i = 1; i <= len; i++) {
		if (!t[now].nt[tem[i]-'a']) t[now].nt[tem[i]-'a'] = ++tot, clear(tot); 
		now = t[now].nt[tem[i]-'a'];
	}
	t[now].cnt = len;
}

void clear(ll now) {if (tag[now] < tim) tag[now] = tim, maxn[now] = 0, t[now].cnt = 0, t[now].fail = 0, memset(t[now].nt, 0, sizeof(t[now].nt)); }

void bfs() {
	queue  q;
	q.push(0);
	while (!q.empty()) {
		ll nt = q.front(); q.pop();
		for (ll i = 0; i < 26; i++) {
			ll son = t[nt].nt[i];
			if (son) {q.push(son); if (!nt) continue; t[son].fail = t[t[nt].fail].nt[i];}
			else t[nt].nt[i] = t[t[nt].fail].nt[i];
		}
	}
	for (ll i = 0; i <= tot; i++) head[i] = -1; cnt = -1;
	for (ll i = 1; i <= tot; i++) add(t[i].fail, i);
	dfs(0);
}

void dfs(ll n) {
	maxn[n] = max(maxn[n], t[n].cnt);
	for (ll i = head[n]; ~i; i = E[i].nt) {
		ll v = E[i].to;
		maxn[v] = maxn[n];
		dfs(v);
	}
}

void add(ll x, ll y) {
	cnt++;
	E[cnt].to = y;
	E[cnt].nt = head[x];
	head[x] = cnt;
}
AC自动机分块字符串

相关

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

题解 Count on a tree II/【模板】树分块

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

python基本数据类型；关于字符串格式化的补充

Java基础-02 字符串(汉字)与16进制字符串转换(无乱码)

C语言判断给定的字符串是否为合法的ip地址的代码-C-J

把字符串a复制到字符串b，利用指针

标签