题目

化简题意：多个环型匹配串在文本串出现次数

做法

我们把环型串备份展开在文本串匹配

当\(parent.len≥len\)时我们要跳父亲，因为要找\(endpos\)

当\(now.len≥len\)时我们就可以统计答案了，为保证时间复杂度，我们不会把环型匹配串分成\(n\)个串匹配，所以\(now.len＞len\)实际上大于的部分我们不需要管了，反正已经找到当前串状态的\(endpos\)直接加就好了

My complete code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef int LL;const LL maxn=3000009;LL nod=1,lst=1,q;LL len[maxn],fail[maxn],val[maxn],sum[maxn],a[maxn],son[maxn][26];LL visit[maxn];char s[maxn];inline void Insert(LL c){ LL np=++nod,p=lst; lst=np; len[np]=len[p]+1; while(p&&!son[p][c]){ son[p][c]=np; p=fail[p]; } if(!p) fail[np]=1; else{ LL q=son[p][c]; if(len[q]==len[p]+1) fail[np]=q; else{ LL nq=++nod; len[nq]=len[p]+1; memcpy(son[nq],son[q],sizeof(son[q])); fail[nq]=fail[q]; fail[np]=fail[q]=nq; while(p&&son[p][c]==q){ son[p][c]=nq; p=fail[p]; } } }++val[lst];}int main(){ scanf(" %s",s+1); for(LL i=1,Len=strlen(s+1);i<=Len;++i){ LL c(s[i]-'a'); Insert(c); } for(LL i=1;i<=nod;++i) ++sum[len[i]]; for(LL i=1,Len=strlen(s+1);i<=Len;++i) sum[i]+=sum[i-1]; for(LL i=1;i<=nod;++i) a[sum[len[i]]--]=i; for(LL i=nod;i>=2;--i) val[fail[a[i]]]+=val[a[i]]; //for(int i=1;i<=nod;++i) // printf("%d(%d) ",a[i],val[a[i]]);printf("\n"); memset(visit,-1,sizeof(visit)); scanf("%lld",&q); while(q--){ scanf(" %s",s+1); LL Len=strlen(s+1); for(LL i=1;i
           
            =Len){ now=fail[now]; L=len[now]; } if(L>=Len&&visit[now]!=q){ ret+=(long long)val[now]; visit[now]=q; } } printf("%lld\n",ret); } return 0;}