【题目链接】 

 

【题目大意】

　　给出一个字符串，然后，给出一个字符串集合，问在该字符串中出现，且不在字符串集合中出现的子串总数。

 

【题解】

　　将集合中所有的子串在自动机上跑，保存匹配到的位置的最长匹配，

　　用于在parent树上计算每个位置的最长匹配，对于一个位置，

　　如果不存在匹配，那么他对答案的贡献就是其value值，

　　如果存在匹配且匹配长度小于其长度那么取其差作为答案的贡献。最后输出即可。

 

【代码】

#include 
     
      #include 
      
       #include 
       
         using namespace std;const int N=200005;char s[N];struct sam{	  int p,q,np,nq,cnt,last,a[N][26],l[N],f[N];	  sam(){cnt=0;last=++cnt;}	  int val(int c){return l[c]-l[f[c]];} 	  void init(){	      cnt=0;last=++cnt;	      memset(a,0,sizeof(a));	      memset(l,0,sizeof(l));	      memset(f,0,sizeof(f));	      memset(b,0,sizeof(b));	      memset(u,0,sizeof(u));	  }	  void extend(int c){		    p=last;np=last=++cnt;l[np]=l[p]+1;		    while(!a[p][c]&&p)a[p][c]=np,p=f[p];		    if(!p)f[np]=1;		    else{			      q=a[p][c];			      if(l[p]+1==l[q])f[np]=q;			      else{				        nq=++cnt;l[nq]=l[p]+1;				        memcpy(a[nq],a[q],sizeof(a[q]));				        f[nq]=f[q]; f[np]=f[q]=nq;				        while(a[p][c]==q)a[p][c]=nq,p=f[p];			      }		    }	  }int b[N],x[N],n;	  void build(){		    scanf("%s",s+1);		    int len=strlen(s+1);n=len;		    for(int i=1;i<=len;i++)extend(s[i]-'a');		    for(int i=1;i<=cnt;i++)b[l[i]]++;		    for(int i=1;i<=len;i++)b[i]+=b[i-1];		    for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i;	  }int u[N];	  void doit(){		    scanf("%s",s+1);		    int p=1,len=strlen(s+1),tmp=0;		    for(int i=1;i<=len;i++){			      int c=s[i]-'a';			      if(a[p][c])p=a[p][c],tmp++,u[p]=max(u[p],tmp);			      else{				        while(p&&!a[p][c])p=f[p];				        if(!p)p=1,tmp=0;				        else tmp=l[p]+1,p=a[p][c],u[p]=max(u[p],tmp);			      }		    } 		}		void solve(){		    long long ans=0;		    for(int i=cnt;i;i--){		        if(u[x[i]]){ 		            u[f[x[i]]]=max(u[x[i]],u[f[x[i]]]);		            if(u[x[i]]