2019 牛客多校 第四场 I、string 广义后缀自动机 + 回文树

#include<stdio.h>
#include<bits/stdc++.h>
#define maxc 28
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
char str[maxn];
int lenn;
struct Suffix_Automaton {
	int len[maxn * 2], //最长子串的长度(该节点子串数量=len[x]-len[link[x]])
	    link[maxn * 2],   //后缀链接(最短串前部减少一个字符所到达的状态)
	    cnt[maxn * 2],    //被后缀连接的数
	    nex[maxn * 2][maxc],  //状态转移(尾部加一个字符的下一个状态)(图)
	    idx, //结点编号
	    last;    //最后结点
	ll num[maxn * 2]; // enpos数（子串出现数量）
	ll a[maxn];		//长度为i的子串出现最大次数

	void init() {	//初始化
		for(int i=1; i<=idx; i++)
			link[i] = len[i] = 0,memset(nex[i],0,sizeof(nex[i]));
		last = idx = 1; //1表示root起始点 空集
	}
//SAM建图
	void extend(int c) {     //插入字符，为字符ascll码值
		int x = ++idx; //创建一个新结点x;
		len[x] = len[last] + 1; //  长度等于最后一个结点+1
		num[x] = 1;  //接受结点子串除后缀连接还需加一
		int p;  //第一个有C转移的结点;
		for (p = last; p && !nex[p][c]; p = link[p])
			nex[p][c] = x;//沿着后缀连接 将所有没有字符c转移的节点直接指向新结点
		if (!p)link[x] = 1, cnt[1]++;  //全部都没有c的转移 直接将新结点后缀连接到起点
		else {
			int q = nex[p][c];    //p通过c转移到的结点
			if (len[p] + 1 == len[q])    //pq是连续的
				link[x] = q, cnt[q]++; //将新结点后缀连接指向q即可,q结点的被后缀连接数+1
			else {
				int nq = ++idx;   //不连续 需要复制一份q结点
				len[nq] = len[p] + 1;   //令nq与p连续
				link[nq] = link[q];   //因后面link[q]改变此处不加cnt
				memcpy(nex[nq], nex[q], sizeof(nex[q]));  //复制q的信息给nq
				for (; p&&nex[p][c] == q; p = link[p])
					nex[p][c] = nq;    //沿着后缀连接 将所有通过c转移为q的改为nq
				link[q] = link[x] = nq; //将x和q后缀连接改为nq
				cnt[nq] += 2; //  nq增加两个后缀连接
			}
		}
		last = x;  //更新最后处理的结点
		
	} 
	
	ll getSubNum() {	//求不相同子串数量
		ll ans = 0;
		for (int i = 2; i <= idx; i++)
			ans += len[i]-len[link[i]];	//一状态子串数量等于len[i]-len[link[i]]
		return ans;
	} 
	
} sam;
struct PAM{//回文树
    int next[maxn][26],fail[maxn],len[maxn],cnt[maxn],S[maxn];
    int id,n,last;
    int newnode(int x){
        for(int i=0;i<26;i++){
            next[id][i]=0;
        }
        cnt[id]=0;
        len[id]=x;
        return id++;
    }
    void init(){
        id=0;
        newnode(0);
        newnode(-1);
        fail[0]=1;
        S[0]=-1;
        last=n=0;
    }
    int getfail(int x){
        while(S[n-len[x]-1]!=S[n]) x=fail[x];
        return x;
    }
    void Insert(int c){
        S[++n]=c;
        int cur=getfail(last);
        if(!next[cur][c]){
            int now=newnode(len[cur]+2);
            fail[now]=next[getfail(fail[cur])][c];
            next[cur][c]=now;
        }
        last=next[cur][c];
        cnt[last]++;
    }
    
}pam;

int main(){
	scanf("%s",str);
	lenn = strlen(str);
	sam.init();
	for(int i=0;i<lenn;i++){
		sam.extend(str[i]-'a');
	}
	sam.last = 1;
	for(int i=lenn-1;i>=0;i--){
		sam.extend(str[i]-'a');
	}
	ll p = sam.getSubNum(); 
	pam.init();
	for(int i = 0;i<lenn;i++){
		pam.Insert(str[i]-'a');
	}
	printf("%lld\n",(p+pam.id-2)/2);
	return 0;
}