Problem 67: Palindromic Tree Construction

Problem Statement: Construct a palindromic tree (EERTREE) for a given string and output the number of distinct palindromic substrings in it.

Input

A single line containing a string of lowercase letters.

Output

Print the number of distinct palindromic substrings.

Examples


Input:
ababa

Output:
5

Solution Explanation

Build the palindromic tree by iterating over the string and adding all palindromic substrings. The tree’s node count (excluding the two roots) gives the distinct count.

Solution in C++


#include 
#include 
#include 
using namespace std;

struct Node{
    int len, link, occ;
    int next[26];
    Node() { 
        len = 0; 
        link = 0; 
        occ = 0; 
        for(int i = 0; i < 26; i++) 
            next[i] = -1;
    }
};

int main(){
    string s; 
    cin >> s;
    int n = s.size();
    vector tree(n + 5);
    int sz = 2, last = 2;
    tree[1].len = -1; 
    tree[1].link = 1;
    tree[2].len = 0; 
    tree[2].link = 1;
    
    auto addLetter = [&](int pos, int &last, int &sz){
        int cur = last;
        int letter = s[pos] - 'a';
        while(true){
            int curlen = tree[cur].len;
            if(pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]) break;
            cur = tree[cur].link;
        }
        if(tree[cur].next[letter] != -1){
            last = tree[cur].next[letter];
            tree[last].occ++;
            return;
        }
        last = ++sz;
        tree[sz].len = tree[cur].len + 2;
        tree[cur].next[letter] = sz;
        if(tree[sz].len == 1){
            tree[sz].link = 2;
        } else {
            cur = tree[cur].link;
            while(true){
                int curlen = tree[cur].len;
                if(pos - curlen - 1 >= 0 && s[pos - curlen - 1] == s[pos]){
                    tree[sz].link = tree[cur].next[letter];
                    break;
                }
                cur = tree[cur].link;
            }
        }
        tree[sz].occ = 1;
    };
    
    for(int i = 0; i < n; i++){
        addLetter(i, last, sz);
    }
    cout << sz - 2 << "\n";
    return 0;
}