回文自动机（回文树）

一、不挣扎了，直接背。

   
   
首先，回文树有何功能？
假设我们有一个串S，S下标从0开始，则回文树能做到如下几点：

1.求串S前缀0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）
2.求串S内每一个本质不同回文串出现的次数
3.求串S内回文串的个数（其实就是1和2结合起来）
4.求以下标i结尾的回文串的个数
   
   
   
这里有个很巧妙的地方，0作为偶数串的根，1作为奇数串的根。
板子：
设字符集大小为m，母串长度为n，则空间复杂度为O(nm)，时间复杂度为O(nlogm)

p：不同回文串的种类，本质不同串的个数；
last：指向 新添加一个字母后所形成的最长回文串（以新添加的字母为右端点）表示的 节点

const int maxn = 100005 ;
const int N = 26 ;

struct Palindromic_Tree {
    int next[maxn][N] ;//这是一棵字典树。
    int fail[maxn] ;
    int cnt[maxn] ; //表示节点i表示的本质不同的串出现的次数
    //（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
    int num[maxn] ; //表示以节点i表示的最长回文串的 最右端点 为回文串结尾的回文串个数
    int len[maxn] ;//len[i]表示节点i表示的回文串的长度（一个节点表示一个回文串）
    int S[maxn] ;
    int last ;//指向新添加一个字母后所形成的最长回文串表示的节点。
    int n ;//表示添加的字符个数。
    int p ;//表示添加的节点个数。

    int newnode ( int l ) 
    {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init () 
    {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;
        fail[0] = 1 ;
    }

    int get_fail ( int x ) 
    {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    void add ( int c ) 
    {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;
        if ( !next[cur][c] ) 
        {
            int now = newnode ( len[cur] + 2 ) ;
            fail[now] = next[get_fail ( fail[cur] )][c] ;
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
    }

    void count () 
    {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
    }
} ; 

二、例题：
（一）
Palindromes and Super Abilities URAL - 1960 ：
After solving seven problems on Timus Online Judge with a word “palindrome” in the problem name, Misha has got an unusual ability. Now, when he reads a word, he can mentally count the number of unique nonempty substrings of this word that are palindromes.
Dima wants to test Misha’s new ability. He adds letters s 1, …, s n to a word, letter by letter, and after every letter asks Misha, how many different nonempty palindromes current word contains as substrings. Which n numbers will Misha say, if he will never be wrong?
Input
The only line of input contains the string s 1… s n, where s i are small English letters (1 ≤ n ≤ 10 5).
Output
Output n numbers separated by whitespaces, i-th of these numbers must be the number of different nonempty substrings of prefix s 1… s i that are palindromes.
Example
input
aba
output
1 2 3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

const int maxn = 100005 ;
const int N = 26 ;

struct Palindromic_Tree {
    int next[maxn][N] ;
    int fail[maxn] ;
    int cnt[maxn] ; 
    int num[maxn] ;
    int len[maxn] ;
    int S[maxn] ;
    int last ;
    int n ;
    int p ;

    int newnode ( int l ) {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init () {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;
        fail[0] = 1 ;
    }

    int get_fail ( int x ) {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    int add ( int c ) {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;
        if ( !next[cur][c] ) {
            int now = newnode ( len[cur] + 2 ) ;
            fail[now] = next[get_fail ( fail[cur] )][c] ;
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
        return p-2;//p从2开始，加入一个字符后变为3
    }

    void count () {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
    }
} pam;

char str[maxn];

int main(void)
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        pam.init();

        for(int i=0;i<len;i++)
        {
            int k=pam.add(str[i]);
            if(i!=0) putchar(' ');
            printf("%d",k);
        }
        putchar('\n');
    }
    return 0;
}

（二）、最长双回文串 HYSBZ - 2565 ：
顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是（ abc 的顺序为 “abc” ，逆序为 “cba” ，不相同）。
输入长度为 n 的串 S ，求 S 的最长双回文子串 T, 即可将 T 分为两部分 X ， Y ，（ |X|,|Y|≥1 ）且 X 和 Y 都是回文串。
Input
一行由小写英文字母组成的字符串S。

Output
一行一个整数，表示最长双回文子串的长度。
Sample Input
baacaabbacabb
Sample Output
12

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const int maxn = 100005 ;
const int N = 26 ;
struct Palindromic_Tree {
    int next[maxn][N] ;
    int fail[maxn] ;
    int cnt[maxn] ;
    int num[maxn] ;
    int len[maxn] ;
    int S[maxn] ;
    int last ;
    int n ;
    int p ;

    int newnode ( int l ) {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init () {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;
        fail[0] = 1 ;
    }

    int get_fail ( int x ) {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    int add ( int c ) {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;
        if ( !next[cur][c] ) {
            int now = newnode ( len[cur] + 2 ) ;
            fail[now] = next[get_fail ( fail[cur] )][c] ;
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
        return len[last];
    }

    void count () {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;

    }
} pam;

char str[maxn];
int f[maxn];

int main(void)
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        pam.init();
        for(int i=0;i<len;i++)
        {
            f[i]=pam.add(str[i]);
        }
        reverse(str,str+len);
        pam.init();
        int ans=0;
        for(int i=0;i<len-1;i++)
        {
            int k=pam.add(str[i]);
            ans=max(ans,k+f[len-i-2]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

（三）、回文串 HYSBZ - 3676 ：
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

Input
输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。

Output

输出一个整数，为逝查回文子串的最大出现值。

Sample Input
【样例输入l】
abacaba

【样例输入2]
www

Sample Output
【样例输出l】
7

【样例输出2]
4
Hint

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：

● a出现4次，其出现值为4：1：1=4

● b出现2次，其出现值为2：1：1=2

● c出现1次，其出现值为l：1：l=l

● aba出现2次，其出现值为2：1：3=6

● aca出现1次，其出现值为1=1：3=3

●bacab出现1次，其出现值为1：1：5=5

● abacaba出现1次，其出现值为1：1：7=7

故最大回文子串出现值为7。

【数据规模与评分】

数据满足1≤字符串长度≤300000。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 300005 ;
const int N = 26 ;

struct Palindromic_Tree {
    int next[maxn][N] ;
    int fail[maxn] ;
    int cnt[maxn] ;
    int num[maxn] ;
    int len[maxn] ;
    int S[maxn] ;
    int last ;
    int n ;
    int p ;
    int newnode ( int l )
    {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init ()
    {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;
        fail[0] = 1 ;
    }

    int get_fail ( int x )
    {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    void add ( int c )
    {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;
        if ( !next[cur][c] )
        {
            int now = newnode ( len[cur] + 2 ) ;
            fail[now] = next[get_fail ( fail[cur] )][c] ;
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
    }

    void count ()
    {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
    }
} pam;

char str[maxn];

int main(void)
{
    scanf("%s",str);
    int len=strlen(str);
    pam.init();
    for(int i=0;i<len;i++)
    {
        pam.add(str[i]);
        //printf("%d\n",len);
    }
    ll ans=0;
    pam.count();
    for(int i=2;i<pam.p;i++)
    {
        ans=max(ans,(ll)pam.cnt[i]*(ll)pam.len[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

（四）、The Problem to Slow Down You UVALive - 7041：
After finishing his homework, our problem setter Federmann decided to kill time by hanging around
online. He found a cool chat room that discusses competitive programming. Federmann has already
joined lot of such chat rooms, but this one is special. Once he entered the chat room, he noticed that
there is an announcement saying “We forbid off-topic messages!”. Federmann thinks that’s quite unusual,
he decided to sit down and join the talk. After watching people discussing different programming
challenges for a while, he found an interesting message saying “No, Federmann won’t prepare another
problem about strings this year.”
“Oh, why do you guys think about that?” Federmann smiled. “Don’t they know I have an Edward
number (the Edward number is something like Erds number, among problem setters) of 3?”
He then thought about something about palindrome, given two strings A and B, what is the number
of their common palindrome substrings? The amount of common palindrome substrings between two
strings is defined as the number of quadruple (p, q, s, t), which satisfies that:

1. 1 ≤ p, q ≤ length(A), 1 ≤ s, t ≤ length(B), p ≤ q and s ≤ t. Here length(A) means the length of
   string A.
2. Ap…q = Bs…t
3. Ap…q is palindrome. (palindrome string is the string that reads the same forward or backward)
   For example, (1, 3, 1, 3) and (1, 3, 3, 5) are both considered as a valid common palindrome substring
   between “aba” and “ababa”.
   Federmann is excited about his new task, and he is just too lazy to write solutions, help him.
   Input
   The first line of the input gives the number of test cases, T. T test cases follow. For each test case,
   the first line contains a string A and the second line contains a string B. The length of A, B will not
   exceed 200000.
   It is guaranteed the input file will be smaller than 8 MB.
   Output
   For each test case, output one line containing ‘Case #x: y’, where x is the test case number (starting
   from 1) and y is the number of common palindrome substrings of A and B.
   Sample Input
   3
   abacab
   abccab
   faultydogeuniversity
   hasnopalindromeatall
   abbacabbaccab
   youmayexpectedstrongsamplesbutnow
   Sample Output
   Case #1: 12
   Case #2: 20
   Case #3: 18
   按照相同路径走道的节点一定是相同的回文串，所以分别以0和1为起点，跑两边dfs。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 200005 ;
const int N = 26 ;

struct Palindromic_Tree {
    int next[maxn][N] ;
    int fail[maxn] ;
    int cnt[maxn] ;
    int num[maxn] ;
    int len[maxn] ;
    int S[maxn] ;
    int last ;
    int n ;
    int p ;
    int newnode ( int l )
    {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init ()
    {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;
        fail[0] = 1 ;
    }

    int get_fail ( int x )
    {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    void add ( int c )
    {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;
        if ( !next[cur][c] )
        {
            int now = newnode ( len[cur] + 2 ) ;
            fail[now] = next[get_fail ( fail[cur] )][c] ;
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
    }

    void count ()
    {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
    }
} pam1,pam2;

char str1[maxn],str2[maxn];
ll ans=0;

void DFS(int x,int y)
{
    for(int i=0;i<26;i++)
    {
        if(pam1.next[x][i]&&pam2.next[y][i])
        {
            ans+=(ll)pam1.cnt[pam1.next[x][i]]*(ll) pam2.cnt[pam2.next[y][i]];
            DFS(pam1.next[x][i],pam2.next[y][i]);
        }
    }
}

int main(void)
{
    int t;
    scanf("%d",&t);
    for(int g=1;g<=t;g++)
    {
        pam1.init();
        pam2.init();
        scanf("%s%s",str1,str2);
        int len1=strlen(str1);
        for(int i=0;i<len1;i++)
            pam1.add(str1[i]);

        int len2=strlen(str2);
        for(int i=0;i<len2;i++)
            pam2.add(str2[i]);

        pam1.count();
        pam2.count();

        ans=0;

        DFS(0,0);
        DFS(1,1);

        printf("Case #%d: %lld\n",g,ans);
    }
    return 0;
}