Submission #682953

#	Time	Username	Problem	Language	Result	Execution time	Memory
682953		79brue	Palindromes (APIO14_palindrome)	C++17	100 / 100	545 ms	38736 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
char str[400002];
ll ans;

void input();
void init();
void dnc();

int main(){
    input();
    init();
    dnc();
    printf("%lld", ans);
}

void input(){
//    n=300000;
//    for(int i=1; i<=n; i++) str[i] = 'a';
    scanf("%s", str+1);
    n = strlen(str+1);
    if(n==1){
        printf("1");
        exit(0);
    }
}

int sa[400005], pos[400005], lcp[400005];
int d;

bool cmp(int i, int j){
    if(pos[i] != pos[j]) return pos[i] < pos[j];
    i += d;
    j += d;
    return (i <= n && j <= n) ? (pos[i] < pos[j]) : (i > j);
}

int temp[600005] = {0};
void constructSA(){
    for(int i=1; i<=n; i++){
        sa[i] = i;
        pos[i] = str[i];
    }
    for(d=1; ; d*=2){
        sort(sa+1, sa+n+1, cmp);
        memset(temp, 0, sizeof(temp));
        for(int i=0; i<=n; i++) temp[i] = 1;
        for(int i=1; i<n; i++)
            temp[i+1] = temp[i] + cmp(sa[i], sa[i+1]);
        for(int i=1; i<=n; i++)
            pos[sa[i]] = temp[i];
        if(temp[n] == n) break;
    }
}

void constructLCP(){
    for(int i=1, k=0; i<=n; i++, k=max(k-1, 0)){
        if(pos[i] == n) continue;

        for(int j=sa[pos[i]+1]; str[i+k]==str[j+k]; k++);
        lcp[pos[i]] = k;
    }
}

int pal[400005];

void manacher(){
    char arr[700005] = {0};
    for(int i=1; i<=n; i++) arr[i*2-1] = arr[i*2+1] = '#', arr[i*2] = str[i];
    arr[0] = 'S', arr[n*2+2] = 'T';
    int maxVal = -1, maxIdx = -1;
    for(int i=1; i<=n*2+1; i++){
        if(maxVal < i) pal[i] = 0;
        else pal[i] = min(pal[maxIdx*2-i], maxVal-i);
        while(arr[i-pal[i]-1] == arr[i+pal[i]+1]) pal[i]++;
        if(i + pal[i] > maxVal) maxVal = i+pal[i], maxIdx = i;
    }

    /// 한 번 나오는 케이스 처리
    for(int i=1; i<=n*2+1; i++){
        if(i%2==1) ans = max(ans, ll(pal[i]+1)/2*2);
        else       ans = max(ans, ll(pal[i])/2*2+1);
    }
}

pair<int, int> tree[1400002];

void init(int i, int l, int r){
    if(l==r){
        tree[i] = make_pair(lcp[l], l);
        return;
    }
    int m = (l+r)>>1;
    init(i*2, l, m);
    init(i*2+1, m+1, r);
    tree[i] = min(tree[i*2], tree[i*2+1]);
}

pair<int, int> query(int i, int l, int r, int s, int e){
    if(r<s || e<l) return make_pair(1000000000, -1);
    if(s<=l && r<=e) return tree[i];
    int m = (l+r)>>1;
    return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}

int tree2[2800002];

void init2(int i, int l, int r){
    if(l==r){
        tree2[i] = l-pal[l];
        return;
    }
    int m = (l+r)>>1;
    init2(i*2, l, m);
    init2(i*2+1, m+1, r);
    tree2[i] = min(tree2[i*2], tree2[i*2+1]);
}

int query2(int i, int l, int r, int s, int e, int v){
    if(r<s || e<l || tree2[i] > v) return 0;
    if(l==r) return l;
    int m = (l+r)>>1;
    int tmp = query2(i*2+1, m+1, r, s, e, v);
    if(tmp) return tmp;
    return query2(i*2, l, m, s, e, v);
}

void init(){
    constructSA();
    constructLCP();
    manacher();
    init(1, 1, n-1);
    init2(1, 1, n+n+1);

    #ifdef TEST
//    for(int i=1; i<=n; i++) printf("%d ", sa[i]); puts("");
//    for(int i=1; i<=n; i++) printf("%d ", lcp[i]); puts("");
//    for(int i=1; i<=n*2+1; i++) printf("%d ", pal[i]); puts("");

    for(int i=1; i<=n; i++) assert(sa[i] == n+1-i);
    for(int i=1; i<n; i++) assert(lcp[i] == i);
    #endif // TEST
}

void dnc(int l, int r){
    if(l>r) return;
    pair<int, int> p = query(1, 1, n-1, l, r);
    dnc(l, p.second-1);
    dnc(p.second+1, r);

    /// 현재 상황 처리하기
    int s = sa[l];
    int e = s + p.first - 1;
    int tmp = query2(1, 1, n+n+1, s+s, s+e, s+s);
    if(!tmp) return;
    ans = max(ans, ll(tmp-(s+s)+1) * ll(r-l+2));
}

void dnc(){
    return dnc(1, n-1);
}

Compilation message (stderr)

palindrome.cpp: In function 'void input()':
palindrome.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%s", str+1);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27