hdu_5769_Substring(后缀数组)

时间：2023-02-11 11:23:32

题目链接：hdu_5769_Substring

题意：

给你一个字符a和一个串b，问你有多少个包括a的字串

题解：

hdu_5769_Substring(后缀数组)

 #include<bits/stdc++.h>

 #define F(i,a,b) for(int i=a;i<=b;++i)

 using namespace std;

 typedef long long ll;

 namespace suffixarray{

     #define FN(n) for(int i=0;i<n;i++)

     const int N =1E5+;//字符串长度

     int rnk[N],sa[N],height[N],c[N];char s[N];

     void getsa(int n,int m,int *x=rnk,int *y=height){

         FN(m)c[i]=;FN(n)c[x[i]=s[i]]++;FN(m)c[i+]+=c[i];

         for(int i=n-;i>=;i--)sa[--c[x[i]]]=i;

         for(int k=,p;p=,k<=n;k=p>=n?N:k<<,m=p){

             for(int i=n-k;i<n;i++)y[p++]=i;

             FN(n)if(sa[i]>=k)y[p++]=sa[i]-k;

             FN(m)c[i]=;FN(n)c[x[y[i]]]++;FN(m)c[i+]+=c[i];

             for(int i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];

             swap(x,y),p=,x[sa[]]=;

             for(int i=;i<n;i++)

             x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;

         }

         FN(n)rnk[sa[i]]=i;

         for(int i=,j,k=;i<n-;height[rnk[i++]]=k)

         for(k=k?k-:k,j=sa[rnk[i]-];s[i+k]==s[j+k];k++);

     }

 }

 using namespace suffixarray;

 int t,ic=,nxt[N];char aim[];

 int main(){

     scanf("%d",&t);

     while(t--)

     {

         scanf("%s%s",aim,s),aim[]-='a'-;

         int len=strlen(s);

         F(i,,len-)s[i]=s[i]-'a'+;

         getsa(len+,);

         for(int i=len-,x=len;i>=;i--)

         {

             if(s[i]==aim[])x=i;

             nxt[i]=x;

         }

         ll ans=;

         F(i,,len)ans+=len-max(nxt[sa[i]],sa[i]+height[i]);

         printf("Case #%d: %lld\n",ic++,ans);

     }

     return ;

 }

相关文章