题目描述
维护字符串,可以执行以下操作(初始为空串)
1:前端插入一个字符
2:后端插入一个字符
3:查询不同本质回文串个数
4:查询所有回文串个数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 8;
int s[N];
struct node{
int len,fail,son[26],siz;
void init(int _len){
memset(son,0,sizeof(son));
fail = siz = 0;
len = _len;
}
}tree[N];
ll num,last[2],ans,L,R;
void init(){
last[0] = last[1] = 0;
ans = 0; num = 1;
L = 1e5 + 8, R = 1e5 + 7;
tree[0].init(0);
memset(s,-1,sizeof(s));
tree[1].init(-1);
tree[0].fail = 1;
}
int getfail(int p,int d){ //后缀链跳跃。复杂度可以看成O(1)
if(d) //新字符在尾部
while(s[R-tree[p].len-1] != s[R])
p = tree[p].fail;
else //新字符在头部
while(s[L+tree[p].len+1] != s[L])
p = tree[p].fail;
return p; //返回结点p
}
void Insert(int x,int d){ //往回文树上插入新结点,这个结点表示一个新回文串
if(d) s[++R] = x; //新字符x插到S的尾部
else s[--L] = x; //新字符x插到S的头部
int father = getfail(last[d],d); //插到一个后缀的子结点上
int now = tree[father].son[x];
if(!now){ //字典树上还没有这个字符,新建一个
now = ++num;
tree[now].init(tree[father].len+2);
tree[now].fail = tree[getfail(tree[father].fail,d)].son[x];
tree[now].siz = tree[tree[now].fail].siz+1;
tree[father].son[x] = now;
}
last[d] = now;
if(R-L+1 == tree[now].len) last[d^1]=now;
ans += tree[now].siz;
}
int main(){
int op,n;
while(scanf("%d",&n)!=EOF){
init();
while(n--){
char c; scanf("%d",&op);
if(op==1) scanf(" %c",&c), Insert(c-'a',0);
if(op==2) scanf(" %c",&c), Insert(c-'a',1);
if(op==3) printf("%lld\n",num-1);
if(op==4) printf("%lld\n",ans);
}
}
return 0;
}