[toph.co] Password Decryption

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Password Decryption
Source            : toph.co
Category          : Data Structure
Algorithm         : Palindromic Tree
Verdict           : Accepted



#include "bits/stdc++.h"  
   
using namespace std;  
   
static const int maxn = 105000;  
   
struct node  
{  
      int next[26];  
      int len;  
      int sufflink;  
      int num;  
} tree[maxn];  
   
int len;  
string s;  
int num;  
int suff;  
   
int maxVowel, maxLen;  
   
int cntVowel[maxn];  
int lengthPal[maxn], blockInd[maxn];  
   
inline bool addLetter(int pos)  
{  
      int curr = suff;  
      int currlen = 0;  
      int let = s[pos] - 'a';  
      while (true)  
      {  
            currlen = tree[curr].len;  
            if (pos-1-currlen >= 0 && s[pos-1-currlen] == s[pos]) break;  
            curr = tree[curr].sufflink;  
      }  
      if (tree[curr].next[let])  
      {  
            suff = tree[curr].next[let];  
            return false;  
      }  
      num++;  
      suff = num;  
      tree[num].len = tree[curr].len + 2;  
      tree[curr].next[let] = num;  
      int length = tree[num].len;  
      int start = pos - length + 1;  
      int tVowel = cntVowel[pos] - (start>0 ? cntVowel[start-1] : 0);  
      if (tVowel <= maxVowel)  
      {  
            lengthPal[start] = length;  
            maxLen = max(maxLen, length);  
      }  
      if (tree[num].len == 1)  
      {  
            tree[num].sufflink = 2;  
            tree[num].num = 1;  
            return true;  
      }  
      while (true)  
      {  
            curr = tree[curr].sufflink;  
            currlen = tree[curr].len;  
            if (pos-1-currlen >= 0 && s[pos-1-currlen] == s[pos])  
            {  
                  tree[num].sufflink = tree[curr].next[let];  
                  break;  
            }  
      }  
      tree[num].num = 1 + tree[tree[num].sufflink].num;  
      return true;  
}  
   
inline void initialize()  
{  
      num = 2;  
      suff = 2;  
      tree[1].len = -1, tree[1].sufflink = 1;  
      tree[2].len = 0, tree[2].sufflink = 1;  
      for (int i = 0; i < maxn; i++)  
      {  
            memset(tree[i].next, 0, sizeof tree[i].next);  
      }  
}  
   
int main()  
{  
      //freopen("in.txt", "r", stdin);  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
      cout.tie(NULL);  
   
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            cin >> len >> maxVowel;  
            cin >> s;  
            initialize();  
            fill(begin(cntVowel), end(cntVowel), 0);  
            fill(begin(lengthPal), end(lengthPal), 0);  
            fill(begin(blockInd), end(blockInd), 0);  
            maxLen = 0;  
            for (int i = 0; i < len; i++)  
            {  
                  if (i > 0) cntVowel[i] = cntVowel[i-1];  
                  if (s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u') cntVowel[i]++;  
                  addLetter(i);  
            }  
            cout << "Case " << tcase << ": ";  
            if (maxLen == 0)  
            {  
                  cout << "not found\n";  
                  continue;  
            }  
            vector <int> vec;  
            for (int i = 0; i < len; i++)  
            {  
                  if (lengthPal[i] == maxLen)  
                  {  
                        vec.push_back(i);  
                  }  
            }  
            string ans = "";  
            int add = 0;  
            while (true)  
            {  
                  char minc;  
                  bool f = false;  
                  if (add >= maxLen) break;  
                  for (int i : vec)   
                  {  
                        int ii = i + add;  
                        if (blockInd[i] == 1) continue;  
                        if (f == false)  
                        {  
                              minc = s[ii];  
                              f = true;  
                        }  
                        else  
                        {  
                              minc = min(minc, s[ii]);  
                        }  
                  }  
                  for (int i : vec)  
                  {  
                        int ii = i + add;  
                        if (blockInd[i] == 1) continue;  
                        if (s[ii] > minc) blockInd[i] = 1;  
                  }  
                  add++;  
            }  
            for (int i : vec)  
            {  
                  if (blockInd[i] == 0)  
                  {  
                        for (int j = 0, k = i; j < maxLen; j++, k++)  
                        {  
                              ans += s[k];  
                        }  
                        break;  
                  }  
            }  
            cout << ans << "\n";  
      }  
}