马拉车&回文树

char str[N],s[N];
int len[N]={0};
int manachr(){
    s[0]='$';
    int n=1;
    for(int i=0;str[i];i++)s[n++]='#',s[n++]=str[i];
    s[n++]='#';s[n]='\0';
    int MAX=0,id=0,mix=0;
    for(int i=1;i<n;i++){
            if(i<mix)len[i]=min(len[2*id-i],mix-i);  
            else len[i]=1;
            while(s[i-len[i]]==s[i+len[i]])len[i]++;
            if(len[i]+i>mix)mix=len[i]+i,id=i,MAX=max(MAX,len[i]);
    }
    for(int i=1;i<n;i++)printf("len[%d]=%d\n",i,len[i]);
    return MAX-1;
} 
//mix  为id为中心 回文串最右端 当i<mix 时  
// 利用回文串的性质  len[i]=len[id-(i-id)]  考虑到i会超过mix 和mix-i取最小

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
typedef long long LL;
struct Tree{
    int last,n,SZ;
    int next[N][26],fail[N],cnt[N],len[N],s[N];
    //cnt 结点为sz的回文串的个数
    // len 结点为sz的回文串长度
    // fail 指向最长的回文后缀结点
    // next 加字符a时指向的结点
    // s存放添加的字符
    void init() {SZ=1,len[1]=-1,s[0]=-1,fail[0]=1;}
    int find(int x) {
        while(s[n-len[x]-1]!=s[n]) x=fail[x];
        return x;
    }
    void add(int t) {
        s[++n]=t;int cur=find(last);
        if(!next[cur][t]) {
            fail[++SZ]=next[find(fail[cur])][t];
            next[cur][t]=SZ,len[SZ]=len[cur]+2;
        }
        last=next[cur][t],++cnt[last];
    }
    LL count() {
        LL res=0;
        for(int i=SZ;i>=0;--i) {
            cnt[fail[i]]+=cnt[i];//回文串个数
            res+=cnt[i];
        }
        return res;
    }
}T;
char str[N];
int slen;
int main()
{
    scanf("%s",str),slen=strlen(str);
    T.init();
    for(int i=0;i<slen;++i) T.add(str[i]-'a');
    printf("%lld\n",T.count());
    cout<<T.SZ<<endl;
    return 0;
}