【模板】回文自动机

struct PAM{
    int fail[N],nxt[N][27],len[N],last,pool;
    void init(){
        for(int i=0;i<=pool;++i){
        	memset(nxt[i],0,sizeof(nxt[i]));
        }
        len[pool=1]=-1;
        len[last=0]=0;
        fail[0]=fail[1]=1;
    }
    int getid(char x){
    	if(x=='*')return 26;
        return x-'a';
    }
    void extend(int x,char *s){
        int p=last,q,cur;
        while(s[x]!=s[x-len[p]-1]&&s[x]!='*'&&s[x-len[p]-1]1='*'){
            p=fail[p];
        }
        cur=nxt[p][getid(s[x])];
        if(!cur){
            cur=++pool;
            q=fail[p];
            while(s[x]!=s[x-len[q]-1]&&s[x]!='*'&&s[x-len[q]-1]!='*'){
                q=fail[q];
            }
            fail[cur]=nxt[q][getid(s[x])];
            len[cur]=len[p]+2;
            nxt[p][getid(s[x])]=cur;
        }
        last=cur;
    }
}pam;