18

// Algorithm        : Palindromic Tree
// Complexity       : O(n)

struct node {
    int next[26];
    int len;
    int sufflink;
} tree[mx];

int max_len, len;
string s;
int num, suff;

void addLetter(int pos) {
    int cur = suff;
    int curlen;
    int let = s[pos] - 'a';
    while (true) {
        curlen = tree[cur].len;
		int id = pos - 1 - curlen;
        if (id >= 0 && s[id] == 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;
		int id = pos - 1 - curlen;
        if (id >= 0 && s[id] == 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;
}

Application:
1. Find maximum length palindromic substring :
   Ans : return max_len
2. Find all distinct palindromic substring :
   Ans : total number of nodes - 2. Set start index & finish
         index in the structure to print the string.
3. How many new palindrome are added?
   Ans : Distinct : add letter & print node num.
         Not Distinct : node num + sufflink.