[Hackerearth] Last Forever

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Last Forever
Source            : Hackerearth
Category          : Data Structure
Algorithm         : Palindromic Tree
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 4e5 + 5;  
  
int Bit[maxn], N;  
  
void update(int pos, int val)  
{  
      if (pos <= 0) return;  
      while (pos <= N)  
      {  
            Bit[pos] += val;  
            pos += (pos & -pos);  
      }  
}  
  
int query(int pos)  
{  
      if (pos > N) pos = N;  
      int sum = 0;  
      while (pos > 0)  
      {  
            sum += Bit[pos];  
            pos -= (pos & -pos);  
      }  
      return sum;  
}  
  
int range_query(int l, int r)  
{  
      return query(r) - query(l-1);  
}  
  
struct Node  
{  
      int Next[30];  
      int len;  
      int sufflink;  
      vector <int> prelink;  
  
};  
  
int len;  
string s;  
int num, suff;  
Node Tree[maxn];  
  
bool addLetter(int pos)  
{  
      int cur = suff, curlen = 0;  
      char 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[ Tree[num].sufflink ].prelink.push_back(num);  
            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];  
                  Tree[ Tree[num].sufflink ].prelink.push_back(num);  
                  break;  
            }  
      }  
      return true;  
}  
  
void init()  
{  
      num = 2; suff = 2;  
      Tree[1].len = -1; Tree[1].sufflink = 1;  
      Tree[2].len = 0; Tree[2].sufflink = 1;  
      Tree[1].prelink.push_back(2);  
}  
  
struct Query  
{  
      int len, id;  
      Query(int len = 0, int id = 0) : len(len), id(id) {}  
};  
  
vector <Query> queries[maxn];  
vector <int> which[maxn];  
int ans[maxn];  
  
void process(int u)  
{  
      for (int v : which[u])  
      {  
            for (Query q : queries[v])  
            {  
                  ans[q.id] = range_query(q.len, N) + (q.len == 0);  
            }  
      }  
}  
  
void dfs(int u = 1)  
{  
      update(Tree[u].len, 1);  
      process(u);  
      for (int v : Tree[u].prelink) dfs(v);  
      update(Tree[u].len, -1);  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(3);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
  
      cin >> s;  
      len = s.size();  
      N = len;  
      reverse(s.begin(), s.end());  
      int q;  
      cin >> q;  
      for (int i = 1; i <= q; i++)  
      {  
            int id, lenn;  
            cin >> id >> lenn;  
            if (id >= len)  
            {  
                  ans[i] = 0 ;  
                  continue;  
            }  
            id = len - id - 1;  
            queries[id].emplace_back(lenn, i);  
      }  
      init();  
      for (int i = 0; i < len; i++)  
      {  
            addLetter(i);  
            which[suff].push_back(i);  
      }  
      dfs();  
      for (int i = 1; i <= q; i++) cout << ans[i] << '\n';  
      return 0;  
}