可以说也是很迷了。最近写的字符串的题都很迷。。
首先看到路牌先写板子AC机，然后迷
然后？？？
回忆一下fail的定义：fail[i]到根形成的字符串是i到根形成的字符串的后缀。
那么大力跳fail硬搞
那么题目询问就变成了求在第y个字符串的那条路径上，有多少个节点fail指向的是第x个字符串的最后一个节点。
根据题解考虑离线搞。
排序一下，这样我们就可以把询问相同y字符串放在一起做。
还是不会做。先把后缀树建出来吧。
诶好像在底部的点都可以对上层的点作出贡献诶，也就是说假如y中的一个点的fail指向x的结尾，那么这个点肯定在x的结尾点的子树里面，那是不是dfs序一下搞个树状数组求答案就行了？
那就再for一次原串，遇到字符就给它+1，删就-1，到了P就看下现在是第几个字符串，这个时候的树状数组就已经把当前字符串的值记录下来了，找到所对应的询问的x串结尾在哪，把它子树的值求出来就行了。
#include#include #include #include #include #include using namespace std;char ss[110000];int slen;int cnt,chuan[110000];struct Trie{ int w[30],fa,fail;}tr[510000];int trlen;void insert(){ scanf("%s",ss+1);slen=strlen(ss+1); trlen=0;cnt=0; int now=0; for(int i=1;i<=slen;i++) { if(ss[i]=='B')now=tr[now].fa; else if(ss[i]=='P')chuan[++cnt]=now; else { int x=ss[i]-'a'+1; if(tr[now].w[x]==0) tr[now].w[x]=++trlen, tr[trlen].fa=now; now=tr[now].w[x]; } }}int list[510000];void bfs(){ int head=1,tail=2;list[head]=0; while(head!=tail) { int now=list[head]; for(int x=1;x<=26;x++) { int son=tr[now].w[x]; if(son!=0) { if(now==0)tr[son].fail=0; else { int p=tr[now].fail; while(p!=0&&tr[p].w[x]==0)p=tr[p].fail; tr[son].fail=tr[p].w[x]; } list[tail]=son; tail++;if(tail==505000)tail=1; } } head++;if(head==505000)head=1; }}//-----------------AC_machine------------------------struct node{ int x,y,next;}a[510000];int len,last[510000];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}int z,l[510000],r[510000];void get_dfs(int x){ l[x]=++z; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; get_dfs(y); } r[x]=z;}void makefailtree(){ len=0;memset(last,0,sizeof(last)); for(int i=1;i<=trlen;i++)ins(tr[i].fail,i); z=0;get_dfs(0);}//-------------make tree and get dfs---------------------int s[510000];int lowbit(int x){ return x&-x;}void change(int x,int k){ while(x<=z) { s[x]+=k; x+=lowbit(x); }}int getsum(int x){ int ret=0; while(x>=1) { ret+=s[x]; x-=lowbit(x); } return ret;}//--------------bit-----------------------struct query{ int x,y,id;}q[110000];int tip;bool cmp(query n1,query n2){ return n1.y