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;
}