[Codeforces] D. Palindrome pairs

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Palindrome pairs
Source            : Codeforces
Category          : Data Structure
Algorithm         : Palindromic Tree
Verdict           : Accepted




#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
  
struct Node  
{  
      int next[27], len, sufflink, num;  
      Node(int len = 0, int sufflink = 0, int num = 0)  
            : len(len)  
            , sufflink(sufflink)  
            , num(num)  
            {  
                  memset(next, 0, sizeof next);  
            }  
};  
  
Node Tree[maxn];  
int num, suff;  
string s;  
  
void init()  
{  
      for (int i = 0; i < maxn; i++) Tree[i] = Node();  
      num = 2; suff = 2;  
      Tree[1].len = -1; Tree[1].sufflink = 1;  
      Tree[2].len = 0; Tree[2].sufflink = 1;  
}  
  
bool addLetter(string &s, int pos)  
{  
      int cur = suff, curlen = 0;  
      int let = s[pos] - 'a';  
      while (true)  
      {  
            curlen = Tree[cur].len;  
            if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]) break;  
            cur = Tree[cur].sufflink;  
      }  
      if (Tree[cur].next[let])  
      {  
            suff = Tree[cur].next[let];  
            return false;  
      }  
      ++num;  
      suff = num;  
      Tree[num].len = Tree[cur].len + 2;  
      Tree[cur].next[let] = num;  
      if (Tree[num].len == 1)  
      {  
            Tree[num].sufflink = 2;  
            Tree[num].num = 1;  
            return true;  
      }  
      while (true)  
      {  
            cur = Tree[cur].sufflink;  
            curlen = Tree[cur].len;  
            if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos])  
            {  
                  Tree[num].sufflink = Tree[cur].next[let];  
                  break;  
            }  
      }  
      Tree[num].num = 1 + Tree[ Tree[num].sufflink ].num;  
      return true;  
}  
  
int prefix[maxn], suffix[maxn];  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> s;  
      int len = s.size();  
      init();  
      for (int i = 0; i < len; i++)  
      {  
            addLetter(s, i);  
            prefix[i] = Tree[suff].num;  
      }  
      reverse(s.begin(), s.end());  
      init();  
      for (int i = 0; i < len; i++)  
      {  
            addLetter(s, i);  
            suffix[len-1-i] = Tree[suff].num;  
      }  
      long long sum_suffix = 0;  
      for (int i = 0; i < len; i++) sum_suffix += suffix[i];  
      long long ans = 0;  
      for (int i = 0; i < len; i++)  
      {  
            sum_suffix -= suffix[i];  
            ans += (prefix[i] * sum_suffix);  
      }  
      cout << ans;  
}