[UVA] 13092 - Fold The String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13092 - Fold The String
Source            : UVA Online Judge
Category          : Data Structure, String
Algorithm         : Palindromic Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 3e6 + 10;  
  
struct Node  
{  
      int next[27];  
      int len;  
      int sufflink;  
      int evenLen;  
      Node(int len = 0, int sufflink = 0, int evenLen = 0)  
            : len(len)  
            , sufflink(sufflink)  
            , evenLen(evenLen)  
            {  
                  memset(next, 0, sizeof next);  
            }  
} Tree[maxn];  
  
string s;  
int len;  
int num;  
int suff;  
  
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[1].evenLen = 0;  
      Tree[2].len = 0; Tree[2].sufflink = 1; Tree[2].evenLen = 0;  
}  
  
bool addLetter(int pos)  
{  
      int cur = suff;  
      int curlen = 0;  
      int let = s[pos] - 'a';  
      while (true)  
      {  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and 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 % 2 == 0) Tree[num].evenLen = Tree[num].len;  
      if (Tree[num].len == 1)  
      {  
            Tree[num].sufflink = 2;  
            return true;  
      }  
      while (true)  
      {  
            cur = Tree[cur].sufflink;  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos])  
            {  
                  Tree[num].sufflink = Tree[cur].next[let];  
                  break;  
            }  
      }  
      if (Tree[num].len % 2 == 1) Tree[num].evenLen = Tree[ Tree[num].sufflink ].evenLen;  
      return true;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int x, y;  
            cin >> x >> y >> s;  
            len = s.size();  
            init();  
            vector <int> evenLen(len);  
            for (int i = 0; i < len; i++)  
            {  
                  addLetter(i);  
                  evenLen[i] = Tree[suff].evenLen;  
            }  
            long long cost = 0;  
            for (int i = len - 1; i >= 0; i--)  
            {  
                  if (evenLen[i] > 0)  
                  {  
                        int h = evenLen[i] / 2;  
                        if (h * x > y)  
                        {  
                              cost += y;  
                              i = i - h + 1;  
                        }  
                        else  
                        {  
                              cost += x;  
                        }  
                  }  
                  else  
                  {  
                        cost += x;  
                  }  
            }  
            cout << "Case " << tcase << ": " << cost << '\n';  
      }  
}