fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. void home()
  11. {
  12.     if(fopen("main.inp","r")) 
  13.     freopen("main.inp","r",stdin),
  14.     freopen("main.out","w",stdout);
  15. }
  16. bool bit(int mask,int i){return (mask>>i)&1;}
  17. int n,l,r;
  18. string s,t;
  19. int newLen[1005][26];
  20. int dp[1005][1005][2],x[1005];
  21. int DigitDP(int cs,int len,int be)
  22. {
  23.     if(cs==0)return 1;
  24.     int &cnt=dp[cs][len][be];
  25.     if(cnt!=-1)return cnt;
  26.     cnt=0;int en=26;if(!be)en=x[cs];
  27.     for(int i=1;i<=en;i++)
  28.     {
  29.         if(newLen[len][i]==t.size()-1)continue;
  30.         cnt=(cnt+DigitDP(cs-1,newLen[len][i],be|(i<en)))%mod;
  31.     }
  32.     return cnt;
  33. }
  34. int Cal(string s)
  35. {
  36.     int d=0;
  37.     for(int i=s.size()-1;i>=0;i--)x[++d]=s[i]-'a'+1;
  38.     memset(dp,-1,sizeof(dp));
  39.     return DigitDP(d,0,0);
  40. }
  41. int mu[1005],ha[1005];
  42. int Get(int j,int i)
  43. {
  44.     return (ha[i]-ha[j-1]*mu[i-j+1]%mod+mod)%mod;
  45. }
  46. void Tcmduc_VOI26()
  47. {
  48.     cin>>n>>s>>t;t=' '+t;
  49.     mu[0]=1;for(int i=1;i<=n;i++)mu[i]=(mu[i-1]*base)%mod;
  50.     for(int i=1;i<t.size();i++)ha[i]=(ha[i-1]*base+t[i]-'a'+1)%mod;
  51.     newLen[0][(int)t[1]-'a'+1]=1;
  52.     for(int i=1;i<t.size()-1;i++)
  53.     {
  54.         for(int c=1;c<=26;c++)
  55.         {
  56.             for(int j=i+1;j>=1;j--)
  57.             {
  58.                 if(Get(1,j)==(Get(i-j+2,i)*base+c)%mod)
  59.                 {
  60.                     newLen[i][c]=j;
  61.                     break;
  62.                 }
  63.             }
  64.         }
  65.     }
  66.     cout<<Cal(s);
  67. }
  68. signed main()
  69. {
  70.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  71.     while(Test--)Tcmduc_VOI26();
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 19292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Mqbu75
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!