LuoguP5212 Substring 题解

题意:(因为很短就贴过来好了)

给定一个字符串init,要求支持两个操作

  • 在当前字符串的后面插入一个字符串
  • 询问字符串s在当前字符串中出现了几次?(作为连续子串)

强制在线。

题解:

查询出现次数明显是一个后缀自动机。

由于有添加操作,因此parent树会实时变化。采用LCT维护一下parent树,就完事了

戳我看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1200050;
char s[3000050]; string chars; int Q, mask;
void decodeWithMask(int mask) {
    scanf("%s",s); chars = s;
    for (int j = 0; j < chars.length();j++) {
        mask = (mask * 131 + j) % chars.length();
        char t = chars[j]; chars[j] = chars[mask]; chars[mask] = t;
    }
}
struct LinkCoverTranslator {
	int ch[MAXN][2], fa[MAXN], w[MAXN], tag[MAXN], st[MAXN];
	void add(int x, int y) {if(x) w[x] += y, tag[x] += y;}
	void pushdown(int x) {if(tag[x]) add(ch[x][0], tag[x]), add(ch[x][1], tag[x]), tag[x] = 0;}
	bool nroot(int x) {return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}
	void rotate(int x) {
		int y = fa[x], z = fa[y], k = (x == ch[y][1]);
		if(nroot(y)) ch[z][y == ch[z][1]] = x; fa[x] = z;
		ch[y][k] = ch[x][k^1]; if(ch[x][k^1]) fa[ch[x][k^1]] = y;
		ch[x][k^1] = y; fa[y] = x;
	}
	void splay(int x) {
		int y = x, z = 0; st[++z] = y;
		while(nroot(y)) st[++z] = y = fa[y]; while(z) pushdown(st[z--]);
		for(; nroot(x); rotate(x)) if(nroot(y = fa[x])) rotate((y==ch[fa[y]][0])^(x==ch[y][0])?x:y);
	}
	void access(int x) {for(int y = 0; x; x = fa[y = x]) splay(x), ch[x][1] = y;}
	void link(int x, int y) {fa[x] = y; access(y); splay(y); add(y, w[x]);}
	void cut(int x) {access(x); splay(x); add(ch[x][0], -w[x]); fa[ch[x][0]] = 0; ch[x][0] = 0;}
} LCT;
struct SuperAnimeMayuri {
	int cnt, last, ch[MAXN][26], fa[MAXN], len[MAXN];
	void insert(int c) {
		int p = last, np = ++cnt; last = np; len[np] = len[p] + 1; LCT.w[np] = 1;
		for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
		if(!p) fa[np] = 1, LCT.link(np, 1);
		else {
			int q = ch[p][c];
			if(len[p] + 1 == len[q]) fa[np] = q, LCT.link(np, q);
			else {
				int nq = ++cnt; len[nq] = len[p] + 1;
				memcpy(ch[nq], ch[q], sizeof ch[q]);
				fa[nq] = fa[q]; LCT.link(nq, fa[q]);
				fa[q] = fa[np] = nq; LCT.cut(q); LCT.link(q, nq); LCT.link(np, nq);
				for(; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
			}
		}
	}
	void build() {
		cnt = last = 1; scanf("%s", s);
		for(int i = 0; i < strlen(s); ++i) insert(s[i]-'A');
	}
	int query() {
		decodeWithMask(mask);
		int p = 1, len = chars.length(); 
		for(int i = 0; i < len; ++i)
			if(!(p = ch[p][chars[i] - 'A'])) return 0;
		LCT.splay(p); return LCT.w[p];
	}
	void add() {
		decodeWithMask(mask);
		int len = chars.length();
		for(int i = 0; i < len; ++i) insert(chars[i] - 'A');
	}
	
} SAM;
int main() {
	scanf("%d", &Q); SAM.build();
	for(char opt[20]; Q--; ) {
		scanf("%s", opt);
		if(opt[0] == 'A') SAM.add();
		else {int ans = SAM.query(); printf("%d\n", ans); mask ^= ans;}
	}
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00