回文自动机
- 本质不同回文串个数=状态数-2
cpp
struct PAM{
static constexpr int ALPHABET_SIZE=26;
struct Node{
int len,link,cnt;// cnt表示以当前字符结尾的不同子串个数(视实际情况而定)
array<int,ALPHABET_SIZE> next;
};
vector<Node> t;
int suff;
string s;
PAM(){
init();
}
void init(){
t.assign(2,Node());//0为奇根，1为偶根
t[0].len=-1;
suff=1;
s.clear();
}
int newNode(){
t.emplace_back();
return t.size()-1;
}
bool add(int c){
int pos=s.size();
s+=c;
c=c-'a';
int cur=suff,curlen=0;
while(true){
curlen=t[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])break;
cur=t[cur].link;
}
if(t[cur].next[c]){
suff=t[cur].next[c];
return false;
}
suff=newNode();
t[suff].len=t[cur].len+2;
t[cur].next[c]=suff;
if(t[suff].len==1){
t[suff].link=1;
t[suff].cnt=1;
return true;
}
while(true){
cur=t[cur].link;
curlen=t[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
t[suff].link=t[cur].next[c];
break;
}
}
t[suff].cnt=1+t[t[suff].link].cnt;
return true;
}
int next(int p,int c){
return t[p].next[c-'a'];
}
int link(int p){
return t[p].link;
}
int len(int p){
return t[p].len;
}
int cnt(int p){
return t[p].cnt;
}
int size(){
return t.size();
}
} pam;