fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const long long MOD=1e9+7;long long f[10005][10005],kq=0;string s;
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  8.     freopen("mstring.inp","r",stdin);
  9.     freopen("mstring.out","w",stdout);
  10.     cin>>s;
  11.     int n=s.size();
  12.     f[0][0]=1;
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         for(int j=1;j<=n;j++)
  16.         {
  17.             f[i][j]=(f[i][j-1]+f[i-1][j]-f[i-1][j-1]+MOD)%MOD;
  18.             if(s[i-1]==s[j-1])f[i][j]=(f[i][j]+f[i-1][j-1]+1)%MOD;
  19.         }
  20.     }
  21.     cout<<f[n][n];
  22.     return 0;
  23. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yBywS6
language:
C++14 (clang 8.0)
created:
7 days 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!