[toph.co] Bomb Disposal Strings

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Bomb Disposal Strings
Source            : toph.co
Category          : Data Structure, String
Algorithm         : Z Algorithm, Palindromic Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
   
using namespace std;  
   
const int maxn = 3000000;  
   
int Z[maxn];  
string string1, string2;  
   
void Z_ALGO(string s)  
{  
    fill(begin(Z), end(Z), 0);  
    int len = s.size();  
    Z[0] = len;  
    int lt = 0, rt = 0;  
    for (int k = 1; k < len; k++)  
    {  
        if (k > rt)  
        {  
            int n = 0;  
            while (n+k < len && s[n] == s[n+k])  
            {  
                n++;  
            }  
            Z[k] = n;  
            if (n > 0)  
            {  
                lt = k;  
                rt = k+n-1;  
            }  
        }  
        else  
        {  
            int p = k - lt;  
            int right_part_len = rt - k + 1;  
            if (Z[p] < right_part_len)  
            {  
                Z[k] = Z[p];  
            }  
            else  
            {  
                int i = rt + 1;  
                while (i < len && s[i] == s[i-k])  
                {  
                    i++;  
                }  
                Z[k] = i - k;  
                lt = k;  
                rt = i-1;  
            }  
        }  
    }  
}  
   
   
string final_string(string s1, string s2)  
{  
    int sze_s1 = s1.size();  
    int sze_s2 = s2.size();  
    string final;   // required string  
    Z_ALGO(s2);  
    int maxLen = 0;  
    for (int i = 1; i < sze_s2; i++)  
        maxLen = max(maxLen, Z[i]);  
    if (maxLen == 0)  
    {  
        final = s1 + s2;  
        return final;  
    }  
    string concate = "";  
    for (int i = 0; i < maxLen; i++)  
        concate += s2[i];  
    concate += "$";  
    concate += s1;  
    int sze_concate = concate.size();  
    Z_ALGO(concate);  
    bool ok = false;  
    for (int i = maxLen+1; i < sze_concate; i++)  
        if (maxLen == Z[i])  
            ok = true;  
    if (!ok)  
    {  
        final = s1 + s2;  
        return final;  
    }  
    final = s1;  
    for (int i = maxLen; i < sze_s2; i++)  
        final += s2[i];  
    return final;  
}  
   
   
struct node  
{  
    int next[27];  
    int len;  
    int sufflink;  
    long long num;  
};  
   
int len;  
string s;  
node tree[maxn];  
int  num;            // node 1 - root with len -1, node 2 - root with len 0  
int suff;            // max suffix palindrome  
long long ans;  
   
bool addLetter(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;  
}  
   
void initTree()  
{  
    num = 2; suff = 2;  
    tree[1].len = -1; tree[1].sufflink = 1;  
    tree[2].len = 0; tree[2].sufflink = 1;  
}  
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);  
    cout.tie(NULL);  
   
    cin >> string1 >> string2;  
    string ss = final_string(string2, string1);  
    string sss = final_string(string1, string2);  
    int len1 = ss.size();  
    int len2 = sss.size();  
    s = (len1 < len2) || (len1==len2 && ss < sss) ? ss : sss;  
    len = s.size();  
    initTree();  
    for (int i = 0; i < len; i++) {  
        addLetter(i);  
        ans += tree[suff].num;  
    }  
    cout << ans << endl;  
    return 0;  
}