题目链接：https://www.hackerrank.com/contests/w22/challenges/sequential-prefix-function
这竟然是一道水题，当时打比赛时竟然没有好好看题。。。悲哀。。。
题目大意
有两种操作，分别是在字符串末尾加上一个字符或者删掉字符串的末尾的字符，要求动态维护kmp。
n≤2?105
解法1
首先可以建出一棵AC自动机，然后我们要求的就是，对于一个点x，我们需要求的是既是x在Trie上的祖先又是x在fail树上的祖先的点中深度最大的点，那么我们先预处理出在Trie每个点的dfn以及这棵子树中dfn最大的dfn(设这个值为r)，然后在fail树上从根节点开始dfs，如果走到某一个点x，如果在它到根节点的路径上存在某一个点u使得 dfnu≤dfnx≤ru ，那么u就可能是我们要找的点，于是我们可以建一棵线段树，每次走进以u为根的子树时，在线段树中的 [dfnu,ru] 插入u（用链表或模链存储），然后走出的时候就删掉，对于查询，我们就在走进这棵子树的时候，查询线段树中到dfn[u]的路径中最大的深度的点，由于链表中最后插入的点的深度一定大于之前插入的，所以我们不用考虑之前插入的点。
解法2
听FTD说fanvree说动态维护kmp有一个log的方法。
首先可以想到一个暴力就是像我们平时建kmp一样不断跳next找可以接下去的点，这个算法之所以是暴力这是因为，我们每次跳的次数可能会达到O(n)级别，我们可以分类讨论一下：
1、next[i]<=n/2，我们可以直接跳
2、next[i]>n/2，观察我们跳掉的部分，其实这一部分也会是下一次跳掉的部分（除非已经跳完了），那么这些次数其实是无用的，因为它们都不可能使我们停止查找，所以可以直接模掉。
我打了第一个解法，打博客时FTD凑上来告诉我，我才知道解法2的。
code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<set>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;
typedef double db;int get(){char ch;int s=0;while(ch=getchar(),ch<'0'||ch>'9');s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return s;
}const int N = 2e+5+10;struct point{int c,x;friend bool operator < (point a,point b){return a.c<b.c;}
};
set<point> s[N];
int now,tot,nxt[N],num[N],dfn[N],r[N],k,dep[N],v[N],fa[N],q[N];
int h[N],n,tv;
struct edge{int x,nxt;
}e[N*22];
int et;
struct node{int l,r,v;
}tree[N*2];void init(){n=get();now=tot=1;s[1].clear();fo(i,1,n){char ch;while(ch=getchar(),ch!='-'&&ch!='+');if (ch=='+'){point u;u.c=get();set<point>::iterator p=s[now].find(u);if(p!=s[now].end())now=(*p).x;else{fa[u.x=++tot]=now;s[now].insert(u);now=u.x;}}else now=fa[now];num[i]=now;}
}void bfs(){int head=0,tail=1;q[1]=1;while(head<tail){int x=q[++head];for(set<point>::iterator p=s[x].begin();p!=s[x].end();p++){int y=(*p).x,c=(*p).c;int tmp=nxt[x];while(tmp&&s[tmp].find(*p)==s[tmp].end())tmp=nxt[tmp];if (!tmp)nxt[y]=1;else nxt[y]=(*(s[tmp].find(*p))).x;q[++tail]=y;}}
}void inse(int &x,int y){e[++et].x=y;e[et].nxt=x;x=et;
}void dfs1(int x){dfn[x]=++k;for(set<point>::iterator p=s[x].begin();p!=s[x].end();p++){dep[(*p).x]=dep[x]+1;dfs1((*p).x);}r[x]=k;
}void build(int &now,int l,int r){tree[now=++tv].v=0;if (l==r)return;int mid=(l+r)/2;build(tree[now].l,l,mid);build(tree[now].r,mid+1,r);
}void change(int now,int l,int r,int x,int y,int v){if (x<=l&&r<=y){inse(tree[now].v,v);return;}int mid=(l+r)/2;if (x<=mid)change(tree[now].l,l,mid,x,y,v);if (y>mid)change(tree[now].r,mid+1,r,x,y,v);
}int getans(int now,int l,int r,int x){int ans=0;if (tree[now].v)ans=dep[e[tree[now].v].x];if (l==r)return ans;int mid=(l+r)/2;int v;if (x<=mid)v=getans(tree[now].l,l,mid,x);else v=getans(tree[now].r,mid+1,r,x);return max(ans,v);
}void del(int now,int l,int r,int x,int y){if (x<=l&&r<=y){tree[now].v=e[tree[now].v].nxt;return;}int mid=(l+r)/2;if (x<=mid)del(tree[now].l,l,mid,x,y);if (y>mid)del(tree[now].r,mid+1,r,x,y);
}void dfs2(int x){v[x]=getans(1,1,tot,dfn[x]);change(1,1,tot,dfn[x],r[x],x);for(int p=h[x];p;p=e[p].nxt)dfs2(e[p].x);del(1,1,tot,dfn[x],r[x]);
}void work(){fo(i,2,tot)inse(h[nxt[i]],i);dfs1(dep[1]=1);int root;build(root,1,tot);dfs2(1);
}void printans(){v[1]=1;fo(i,1,n)printf("%d\n",v[num[i]]-1);
}int main(){init();bfs();work();printans();return 0;
}