1 条题解

  • 0
    @ 2026-1-15 11:42:59

    #include <bits/stdc++.h>
    #define N 341467
    #define count scx
    using namespace std;
    
    typedef long long ll;
    
    char s[N], *ptr;
    int d[N][26], fail[N], val[N], count[N];
    int i, cnt = 1, p, last = 0; ll ans = 0;
    
    inline void up(ll &x, const ll y) {x < y ? x = y : 0;}
    int get_fail(int x) {for(; *(ptr - (val[x] + 1)) != *ptr; x = fail[x]); return x;}
    
    void extend(int x){
        p = get_fail(last);
        int &q = d[p][x];
        if(!q) {fail[++cnt] = d[get_fail(fail[p])][x]; val[q = cnt] = val[p] + 2;}
        ++count[last = q];
    }
    
    int main(){
        s[0] = val[1] = -1; fail[0] = 1; scanf("%s", s + 1);
        for(ptr = s; *ptr; ++ptr) extend(*ptr - 'a');
        for(i = cnt; i > 1; --i) count[fail[i]] += count[i];
        for(i = 2; i <= cnt; ++i) up(ans, (ll)count[i] * val[i]);
        printf("%lld\n", ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    5341
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    3
    已通过
    1
    上传者