[Spoj] LPS - Longest Palindromic Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : LPS - Longest Palindromic Substring
Source            : Spoj
Category          : Data Structure
Algorithm         : Palindromic Tree
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
 
const int mx = 105000;
 
 
struct node {
    int next[26];
    int len;
    int sufflink;
} tree[mx];
 
int max_len;
 
int len;
string s;
 
int num;
int suff;
 
void addLetter(int pos)
{
    int cur = suff;
    int curlen;
    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;
    }
    num++;  // create new node number
    suff = num;
    tree[num].len = tree[cur].len + 2;  // new node
    tree[cur].next[let] = num;
    max_len = max(tree[num].len, max_len);
    if (tree[num].len == 1)
    {
        tree[num].sufflink = 2;
        return;
    }
    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;
        }
    }
    return;
}
 
void init_palindrome_tree()
{
    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::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> len >> s;
    max_len = -1;
    init_palindrome_tree();
    for (int i=0; i<len; i++)
    {
        addLetter(i);
    }
    cout << max_len << endl;
}