萌新初学回文自动机求助
查看原帖
萌新初学回文自动机求助
490978
小超手123楼主2023/12/26 18:56
#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
string s;
int n, cnt = 1, lst, now, ans;
int fail[N], tree[N][30], len[N], sum[N];
int getfail(int u, int p) { 
    while(p - len[u] - 1 < 0 || s[p - len[u] - 1] != s[p])
        u = fail[u];
    return u;
}
void insert(char c, int id) { 
    int p = getfail(now, id); 
    if(!tree[p][c - 'a']) { 
        fail[++cnt] = tree[getfail(fail[p], id)][c - 'a'];
        tree[p][c - 'a'] = cnt;
        len[cnt] = len[p] + 2;
    }
    now = tree[p][c - 'a'];
    sum[cnt]++;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> s;
    n = s.length();
    fail[0] = 1, len[1] = -1;
    for(int i = 0; i < n; i++) insert(s[i], i);
    for(int i = cnt; i >= 0; i--) {
        sum[fail[i]] += sum[i];
        ans = max(ans, sum[i] * len[i]);
    }
    cout << ans;
    return 0;
}
/*
qpppppppwowpppppq

*/
2023/12/26 18:56
加载中...