题意：
此题为NOI2017D1T2，题目链接如下
https://www.lydsy.com/JudgeOnline/upload/Noi2017D1.pdf
题解：
本题的做法实际上比较暴力。观察数据范围，我们发现k很小，那么这意味着我们将两只蚯蚓合并的时候，只有首尾的k个字符会发生影响，那么我们只需要把新增加的贡献加上即可，删除同理，只不过变成减掉。
那么拼接起来产生的贡献（或消除掉的贡献），实际上就是用k^2的效率暴力枚举起点和终点，然后删掉它对应的字符串的答案。这个操作我们可以使用hash表来维护，但是考虑到容易起冲突，我们改成使用trie树维护。
询问的时候，注意一些细节处理，为了使效率高，我们还需要维护trie树上某个节点，删掉最前面一个字符之后会跳到哪个位置（方便快速查询），这样总复杂度就可以接受了。
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; const int k=50,mod=998244353; int n,m,len,t[8][20000002]; long long ans; char ch[10000002]; typedef struct{ int w,las,nex; }P; P p[200002]; int read() { int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-'){w=-1;ch=getchar();} while(ch>='0' && ch<='9'){data=data*10+ch-'0';ch=getchar();} return data*w; } int main() { n=read();m=read(); for (int i=1;i<=n;i++) { p[i].w=read();p[i].las=p[i].nex=-1; if (!t[p[i].w][0])t[p[i].w][0]=++len; t[0][t[p[i].w][0]]++; } while(m--) { int u; u=read(); if (u==1) { int a,b,c,root;bool u; a=read();b=read(); p[a].nex=b;p[b].las=a; for (int i=a;i!=-1;i=p[i].las) { c=u=root=0; for (int j=i;c<k&&j!=-1;j=p[j].nex) { if (!t[p[j].w][root]) { t[p[j].w][root]=++len; if (t[7][root]==-1 || !t[p[j].w][t[7][root]]) t[7][len]=-1; else t[7][len]=t[p[j].w][t[7][root]]; } root=t[p[j].w][root]; if (j==b)u=1;t[0][root]+=u; c++; } if (!u)break; } } else if (u==2) { int a,b,c,root;bool u; a=read();b=p[a].nex; for (int i=a;i!=-1;i=p[i].las) { c=u=0;root=0; for (int j=i;c<k&&j!=-1;j=p[j].nex) { root=t[p[j].w][root]; if (j==b)u=1;t[0][root]-=u; c++; } if (!u)break; } p[a].nex=p[b].las=-1; } else { int a,l,root=0;ans=0; scanf("%s",ch);a=read();l=strlen(ch); for (int i=0;i<a;i++) { root=t[ch[i]-48][root];if (!root)goto ccj; } ans=t[0][root]; for (int i=a;i<l;i++) { root=t[7][root];if (root<0){ans=0;goto ccj;} root=t[ch[i]-48][root];if (!root){ans=0;goto ccj;} ans=ans*t[0][root]%mod; } ccj:printf("%lld ",ans); } } return 0; }