無名（noname）

【问题描述】

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

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

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

友情提示：如果你过不了样例，请注意是不同的子串。

【输入文件】

一共3行。

第一行母串S；

第二行串A；

第三行串B。

【输出文件】

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

【输入样例】

abababab

【输出样例】

【数据规模和约定】

100%:

length(S)<=2000;

length(A)<=2000;

length(B)<=2000;

30%:都少个0

字符串hash

首先，枚举每一个后缀是否前缀为A，front[i]表示i~l-1的前缀是否为A

同理处理出bside[i]表示0~i的后缀是否为B

枚举左右端点，可知当2个数组都为1才为一个解

但是解不能重复

于是用字符串hash，就是将字符串转数

hash[i]表示0~i的hash值

hash[i]=((hash[i-1]*p+idx(s[i]))%Mod

Mod和p都要慎重考虑，p取31，Mod取1e7+7

那么l~r的hash值为:hash(l~r)=(hash[r]-hash[l-1]*p^(r-l+1)+Mod)%Mod

一般Mod取1e9+7，但是这里要用bool数组，所以取1e7+7

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int p=,Mod=;

 int l,la,lb,front[],bside[];

 char s[],A[],B[];

 long long pow[],hash[],ans;

 bool vis[];

 bool ask(int x,int y)

 {

     long long h=(hash[y]-(hash[x-]*pow[y-x+]%Mod)+Mod)%Mod;

     if (vis[h]==)

     {

      vis[h]=;

      return ;

     }

     else

     {

      return ;

     }

 }

 int main()

 {int i,j;

 //freopen("noname.in","r",stdin);

 //freopen("noname.out","w",stdout);

     cin>>s;

     cin>>A;

     cin>>B;

     l=strlen(s);

     la=strlen(A);

     lb=strlen(B);

      for (i=;i<l;i++)

      {

         for (j=;j<=la,j+i-<l;j++)

          if (A[j-]!=s[i+j-]) break;

         if (j>la)

          front[i]=;

      }

      for (i=l-;i>=;i--)

      {

         for (j=;j<=lb,i-j+>=;j++)

         if (B[lb-j]!=s[i-j+]) break;

         if (j>lb)

          bside[i]=;

      }

      hash[]=(int)s[]-;

     for (i=;i<=l;i++)

     {

       hash[i]=(hash[i-]*p+(int)s[i-]-)%Mod;

     }

     pow[]=;

      for (i=;i<=l;i++)

       pow[i]=(pow[i-]*p)%Mod;

     for (i=;i<l;i++)

     {

      for (j=i+max(la,lb)-;j<l;j++)

      if (front[i]&&bside[j])

        if (ask(i+,j+)) ans++;

     }

 cout<<ans;

 }

巴特西