原题链接

发现 k<=50 ，在插入和删除时最多会影响不超过 k2 个串，用链表实现插入和删除,然后只需用哈希表维护每个长度不超过k的串的出现次数，哈希的话可以先用比较大的范围的值处理冲突，再映射到1e8的桶里统计。

考虑复杂度。

首先在删除时由于保证了 c<=1000 所以这部分复杂度是O(ck2)的。

插入时，如果插入操作很慢只有可能是连接两个长度不小于k的串，而长度不小于k的串最多有n/k个，所以这部分复杂度是O(nk)的

所以总复杂度是O(nk+ck2+|s|)。

#include
#include
#include
#include
#include
#include
#include
#include
#include

inline ul qpow(ul a,int n)
{
ul ans=1;
for(;n;n>>=1,a=a*a) if(n&1) ans=ans*a;
return ans;
}

inline void insert(ul x)
{
ul m=x%mod2;
int u=fir[m];
if(!u)
{
fir[m]=++cnt; hax[cnt]=x;
num[cnt]++; return ;
}
if(hax[u]==x) {num[u]++;return ;}
while(nex[u])
{
u=nex[u];
if(hax[u]==x) {num[u]++; return ;}
}
cnt++;
nex[u]=cnt;
hax[cnt]=x; num[cnt]++;
}

inline void del(ul x)
{
ul m=x%mod2;
int u=fir[m];
while(u)
{
if(hax[u]==x) {num[u]--;return ;}
u=nex[u];
}
}

inline int query(ul x)
{
ul m=x%mod2;
int u=fir[m];
while(u)
{
if(hax[u]==x) return num[u];
u=nex[u];
}
return 0;
}
char a[10000050];
int n,m;

int main()
{
#ifndef ONLINE_JUDGE
freopen("queue.in","r",stdin);freopen("queue.out","w",stdout);
#endif
int i,j,opt,x,y,k;
read(n);read(m);
for(i=1;i<=n;++i)
{
read(opt),leng[i]=opt+48;
ul has=leng[i]-48u;
insert(has);
}
while(m--)
{
read(opt);
if(opt==1)
{
read(x);read(y);//--x y--
tail[x]=y;head[y]=x;
int u=x,v;
for(i=1;i<=50-2&&head[u];++i) u=head[u];
for(;u!=y;u=tail[u])
{
bool can=0;
v=u;
ul has=0;
has=leng[u]-48u;
for(i=1;i<50;++i)
{
v=tail[v];
if(!v) break;
has=has*bas+leng[v]-48u;
if(v==y||can)
{
can=1;
insert(has);
}
}
}
}
else if(opt==2) // --x || y--
{
read(x);
int u=x,v;
y=tail[x];
for(i=1;i<=50-2&&head[u];++i) u=head[u];
for(;u!=y;u=tail[u])
{
bool can=0;
v=u;
ul has=leng[u]-48u;
for(i=1;i<50;++i)
{
v=tail[v];
if(!v) break;
has=has*bas+leng[v]-48u;
if(v==y||can)
{
can=1;
del(has);
}
}
}
head[y]=0;tail[x]=0;
}
else
{
ll ans=1;
scanf("%s",a);read(k);
int len=strlen(a);

        ul has=0,powbas=qpow(bas,k-1);  
        for(i=0;i<k;++i) has=has\*bas+a\[i\]-48u;  
        ans=ans\*(ll)query(has);  
        for(i=1;i<=len-k;++i)  
        {  
            has=(has-(a\[i-1\]-48u)\*powbas)\*bas+a\[i+k-1\]-48u;  
            ans=ans\*(ll)query(has)%mod;  
        }  
        printf("%lld\\n",ans);  
    }  
}  
return 0;  

}