[测试题]無名（noname）

Description

因为是蒯的题所以没想好名字，为什么要用繁体呢？去看《唐诗三百首》吧！

题意很简单，给你一个串，求他有多少个不同的子串，满足前缀为A，后缀为B。

需要注意的是，串中所有的字母都是小写字母。

Input

一共3行。

第一行母串S；

第二行串A；

第三行串B。

Output

一个数，即有多少不同的子串。

Sample Input

abababab

Sample Output

Hint

100%:

length(S)<=2000;

length(A)<=2000;

length(B)<=2000;

30%:都少个0。

题解

我们可以预处理出所有$A$串和$B$串在$S$中的位置。

找到合法的串，我们可以去找前缀和后缀的位置，取出中间的部分用$hash$判重就好了。

 #include<set>

 #include<map>

 #include<cmath>

 #include<ctime>

 #include<queue>

 #include<stack>

 #include<vector>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const LL N=;

 const LL MOD=1e8+;

 LL Max(const LL &a,const LL &b) {return a>b ? a:b;}

 LL Min(const LL &a,const LL &b) {return a<b ? a:b;}

 char S[N+],A[N+],B[N+];

 LL ls,la,lb;

 bool vis[N+];

 LL ans;

 LL q[N+],hash[N+];

 bool pd[MOD+];

 bool find_hash(LL x)

 {

     if (pd[x]) return false;

     pd[x]=;

     return true;

 }

 int main()

 {

     S[]=A[]=B[]='$';

     scanf("%s%s%s",S+,A+,B+);

     ls=strlen(S)-,la=strlen(A)-,lb=strlen(B)-;

     q[]=;

     for (LL i=;i<=ls;i++) q[i]=(q[i-]*)%MOD;

     for (LL i=;i<=ls;i++) hash[i]=(hash[i-]*+S[i]-'a'+)%MOD;

     for (LL i=;i<=ls;i++) if (S[i]==B[])

     {

         LL j;

         for (j=;j<=lb;j++) if (S[i+j-]!=B[j]) break;

         if (j>lb) vis[i]=;

     }

     for (LL i=;i<=ls;i++) if (S[i]==A[])

     {

         LL j;

         for (j=;j<=la;j++) if (S[i+j-]!=A[j]) break;

         if (j>la)

         {

             for (LL j=Max(i,la-lb+i);j<=ls;j++) if (vis[j])

             {

                 LL r=j+lb-;

                 if (find_hash((hash[r]+MOD-hash[i-]*q[r-i+]%MOD)%MOD)) ans++;

             }

         }

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西