字符串-回文自动机

回文自动机学习博客：https://blog.csdn.net/u013368721/article/details/42100363 （我喜欢这个代码风格）
这个思想讲解的更好：https://blog.csdn.net/lwfcgz/article/details/48739051
思路：
对A ，B跑一次回文自动机，然后分别搜偶数长度的串， 奇数长度串。

Code：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int AX = 2e5+666;
char a[AX];
char b[AX];
LL res;
struct Ptree{
    int next1[AX][26];
    int fail[AX];
    LL cnt[AX];
    int num[AX];
    int len[AX];
    int s[AX];
    int last;
    int n , p ;

    int newnode( int l ){
        for( int i = 0 ; i < 26 ; i++ ){
            next1[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 insert( char c ){
        int id = c - 'a';
        s[++n] = id;
        int cur = get_fail( last );
        if( !next1[cur][id] ){
            int now = newnode( len[cur] + 2 );
            fail[now] = next1[get_fail(fail[cur])][id];
            next1[cur][id] = now;
            //num[now] = num[fail[now]] + 1 ;
        }
        last = next1[cur][id];
        cnt[last]++;
    }

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

void dfs( int u1 , int u2 ){
    res += A.cnt[u1] * B.cnt[u2];
    for( int i = 0 ; i < 26 ; i++ ){
        if( A.next1[u1][i] > 1 && B.next1[u2][i] > 1 ){
            dfs( A.next1[u1][i] , B.next1[u2][i] );
        }
    }
    return ;
}

int main(){
    res = 0 ;
    scanf("%s%s",a,b);
    A.init();
    int lena = strlen(a);
    int lenb = strlen(b);
    for( int i = 0 ; i < lena ; i ++ ){
        A.insert(a[i]);
    }
    A.count();

    B.init();
    for( int i = 0 ; i < lenb ; i ++ ){
        B.insert(b[i]);
    }
    B.count();

    for( int i = 0 ; i < 26 ; i++ ){
        if( A.next1[0][i] > 1 && B.next1[0][i] > 1 ){ //按理说不等于0就行，但是我不写>1一直wa1在test4.可能因为我对回文机还不熟悉，有什么极端情况没考虑到。
            dfs( A.next1[0][i] , B.next1[0][i] );
        }
    }
    for( int i = 0 ; i < 26 ; i++ ){
        if( A.next1[1][i] > 1 && B.next1[1][i] > 1 ){
            dfs( A.next1[1][i] , B.next1[1][i] );
        }
    }
    cout << res << endl;

    return 0 ;
}