1 条题解

  • 1
    @ 2022-8-25 10:01:46
    #define Sigma 30
    #define MAXN 500010
    #define LL long long
    
    using namespace std ;
    int N, M ; LL ans ; char S[MAXN], T[MAXN] ;
    struct PAM{
    	int rt0, rt1, last, sz, f[MAXN] ;
    	int trie[MAXN][Sigma], pre[MAXN], len[MAXN] ;
    	void Init(){
    		sz = -1, rt0 = ++ sz, rt1 = ++ sz ; 
    		pre[rt0] = pre[rt1] = rt1, len[rt0] = 0, len[rt1] = -1, last = rt0 ; 
    	} 
    	void Insert(int x, int p, char *s){
    		int u = last ; 
    		while (s[p] != s[p - len[u] - 1]) u = pre[u] ; 
    		if (!trie[u][x]){
    			int newq = ++ sz, fa = pre[u] ; 
    			while (s[p] != s[p - len[fa] - 1]) fa = pre[fa] ;
    			pre[newq] = trie[fa][x], trie[u][x] = newq, len[newq] = len[u] + 2 ;
    		}
    		last = trie[u][x], f[last] ++ ; 
    	}
    }P, Q ;
    void dfs(int x, int y){
    	if (x + y > 2) ans += 1ll * P.f[x] * Q.f[y] ; 
    	for (int i = 1 ; i <= 26 ; ++ i)
    		if (P.trie[x][i] && Q.trie[y][i]) dfs(P.trie[x][i], Q.trie[y][i]) ;
    }
    int main(){
    	P.Init(), Q.Init() ;
    	cin >> (S + 1) >> (T + 1) ; 
    	N = strlen(S + 1), M = strlen(T + 1) ;
    	for (int i = 1 ; i <= N ; ++ i) P.Insert(S[i] - 'A' + 1, i, S) ;
    	for (int i = 1 ; i <= M ; ++ i) Q.Insert(T[i] - 'A' + 1, i, T) ;
    	for (int i = P.sz ; i ; -- i) P.f[P.pre[i]] += P.f[i] ; 
    	for (int i = Q.sz ; i ; -- i) Q.f[Q.pre[i]] += Q.f[i] ; 
    	dfs(1, 1) ; dfs(0, 0) ; cout << ans<< endl ; return 0 ;
    }
    
    • 1

    信息

    ID
    4480
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    11
    已通过
    6
    上传者