fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long dp1[1001][1001], dp2[1001][1001], ans[1001][1001], is_palin[1001][1001];
  4. int main()
  5. {
  6.     //freopen("input14.txt","r",stdin);
  7.     //freopen("output14.txt","w",stdout);
  8.     string t;
  9.     cin >> t;
  10.     string s = '$' + t;
  11.     int n = s.size();
  12.     for(int i = 0; i < s.size(); i++)
  13.     {
  14.         for(int j = 0; j < s.size(); j++)
  15.         {
  16.             dp1[i][j] = dp2[i][j] = ans[i][j] = is_palin[i][j] = 0;
  17.         }
  18.     }
  19.     for(int k = 1; k < n; k++)
  20.     {
  21.         for(int j = k, i = 1; j < n; j++, i++)
  22.         {
  23.             if(s[i] == s[j])
  24.             {
  25.                 if(j - i <= 2)
  26.                 {
  27.                     is_palin[i][j] = 1;
  28.                 }
  29.                 else
  30.                 {
  31.                     if(is_palin[i + 1][j - 1])
  32.                     {
  33.                         is_palin[i][j] = 1;
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     for(int k = 1; k < n; k++)
  40.     {
  41.         for(int j = k, i = 1; j < n; i++, j++)
  42.         {
  43.             if(is_palin[i][j])
  44.             {
  45.                 dp1[i][j] = dp1[i][j - 1] + 1;
  46.             }
  47.             else
  48.             {
  49.                 dp1[i][j] = dp1[i][j - 1];
  50.             }
  51.         }
  52.     }
  53.     for(int k = n - 1; k >= 1; k--)
  54.     {
  55.         for(int j = k, i = k; i >= 1; i--)
  56.         {
  57.             if(is_palin[i][j])
  58.             {
  59.                 dp2[i][j] = dp2[i + 1][j] + 1;
  60.             }
  61.             else
  62.             {
  63.                 dp2[i][j] = dp2[i + 1][j];
  64.             }
  65.         }
  66.     }
  67.     for(int k = 1; k < n; k++)
  68.     {
  69.         for(int j = k, i = 1; j < n; i++, j++)
  70.         {
  71.             if(s[i] == s[j] && i != j)
  72.             {
  73.                 if(j - i == 1) ans[i][j] = 1;
  74.                 else if(j - i == 2) ans[i][j] = 3;
  75.                 else
  76.                 {
  77.                     ans[i][j] = 1 + ans[i + 1][j - 1] + dp1[i + 1][j - 2] + dp2[i + 2][j - 1];
  78.                     if(is_palin[i + 1][ j - 1]) ans[i][j] += 2;
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     long long result(0);
  84.     for(int i = 1; i < n; i++)
  85.     {
  86.         for(int j = 1; j < n; j++)
  87.         {
  88.             result += ans[i][j];
  89.         }
  90.     }
  91.     cout << result << endl;
  92. }
Success #stdin #stdout 0s 46552KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/Zx15BO
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!