제출 #1177774

#제출 시각아이디문제언어결과실행 시간메모리
1177774kitetrietrie회문 (APIO14_palindrome)C++20
0 / 100
13 ms28524 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const ll base = 31;
const ll mod = 1e9 + 7;
string S;
int D_odd[N], D_even[N], n;
ll hashT[N], P10[N];

struct node{
    int l, r;
    ll s;
};

map<int,node> mp[N];
map<int,bool> F[N];

ll Ans = 0;

ll get(int i,int j) {
    return (hashT[j] - (hashT[i - 1] * P10[j - i + 1] % mod) + mod) % mod;
}


void Cal_D_odd(){
    int L = 1;
    int R = 0;
    for(int i = 1 ; i <= n ; ++i){
        if(i > R) D_odd[i] = 0;
        else D_odd[i] = min(R - i,D_odd[R - i + L]);
        while(i - D_odd[i] - 1 > 0 && i + D_odd[i] + 1 <= n && S[i - D_odd[i] - 1] == S[i + D_odd[i] + 1]){
            D_odd[i]++;
        }
        if(i + D_odd[i] > R){
            R = i + D_odd[i];
            L = i - D_odd[i];
        }
        int sz = D_odd[i] * 2 + 1;
        //cout << i << "." << sz << "====\n";
        if(sz > 0){
            ll s = get(i - D_odd[i], i + D_odd[i]);
            //cout << i - D_odd[i] << ' ' << i + D_odd[i] << ' ' << s << '\n';
            int _l = i - D_odd[i];
            int _r = i + D_odd[i];

            if(_l <= _r && !F[sz][s]){
                mp[sz][s] = {_l,_r,1};
                F[sz][s] = 1;
            }
            else
                mp[sz][s].s += 1;
        }
    }
}

void Cal_D_even(){
    int L = 1;
    int R = 0;
    for(int i = 1 ; i < n ; ++i){
        int j = i + 1;
        if(j > R) D_even[i] = 0;
        else D_even[i] = min(R - j + 1,D_even[R + L - j]);
        while(i - D_even[i] > 0 && j + D_even[i] <= N && S[i - D_even[i]] == S[j + D_even[i]])
            D_even[i]++;
        if(i + D_even[i] > R){
            R = i + D_even[i];
            L = j - D_even[i];
        }
        int sz = D_even[i] * 2;
        if(sz > 0){
            ll s = get(j - D_even[i], i + D_even[i]);
            //cout << D_even[i] << ' ' << j - D_even[i] << ' ' << i + D_even[i] << ' ' << s << '\n';
            int _l = j - D_even[i];
            int _r = i + D_even[i];

            if(_l <= _r && !F[sz][s]){
                mp[sz][s] = {_l,_r,1};
                F[sz][s] = 1;
            }
            else
                mp[sz][s].s += 1;
        }

    }
}


int main(){
    cin >> S;
    n = S.length();
    S = ' ' + S;
    P10[0] = 1;
    for(int i = 1 ; i <= n ; ++i) P10[i] = P10[i - 1] * base % mod;
    for(int i = 1 ; i <= n ; ++i) hashT[i] = hashT[i - 1] * base + (S[i] - 'a' + 1) % mod;
    Cal_D_even();
    Cal_D_odd();

    for(ll i = n ; i >= 1 ; --i){
        //cout << i << "====\n";
        for(pair<int,node> j : mp[i]){
            Ans = max(Ans, i * j.second.s);
            //cout << j.second.l << ' ' << j.second.r << ' ' << j.second.s << '\n';
        }
        if(i - 2 >= 1)
        for(pair<int,node> j : mp[i])
        {
            ll s = get(j.second.l + 1,j.second.r - 1);
            if(!F[i - 2][s]){
                mp[i - 2][s].s += mp[i][j.first].s;
                mp[i - 2][s].l = j.second.l + 1;
                mp[i - 2][s].r = j.second.r - 1;
                F[i - 2][s] = 1;
            }
            else{
                mp[i - 2][s].s += mp[i][j.first].s;
            }
        }
    }
    cout << Ans ;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...