제출 #24726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24726		Extazy	회문 (APIO14_palindrome)	C++14	0 / 100	1000 ms	22636 KiB

palindrome

/*
example test starts
abacaba

www
example test ends
*/
#include <bits/stdc++.h>
#define left aklhglahjkga
#define right qioyhqhgjkqh

using namespace std;

const unsigned long long B1 = 137, B2 = 139, MOD = (1e9) + 7;
const int N = 300007;

struct rolling_hash {
    unsigned long long h1,h2;
    void initialize() {
        h1=0;
        h2=0;
    }
    void append(char a) {
        h1*=B1;
        h2*=B2;
        h1+=a;
        h2+=a;
        h1%=MOD;
        h2%=MOD;
    }
    bool operator ==(const rolling_hash &a) const {
        return (h1==a.h1 && h2==a.h2);
    }
    bool operator !=(const rolling_hash &a) const {
        return !(h1==a.h1 && h2==a.h2);
    }
};

int n;
char a[N];
rolling_hash ph[N],sh[N];
int sa[N],lcp[N];
long long ans;
int left[N],right[N];
stack < int > s;
unsigned long long pw1[N],pw2[N];
int longest[N];

rolling_hash get_hash(int l, int r) {
    rolling_hash hl=ph[l-1],hr=ph[r];
    hl.h1*=pw1[r-l+1];
    hl.h1%=MOD;
    hl.h2*=pw2[r-l+1];
    hl.h2%=MOD;
    
    hr.h1-=hl.h1;
    hr.h1+=MOD;
    hr.h1%=MOD;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;

    return hr;
}

rolling_hash get_reversed_hash(int l, int r) {
    rolling_hash hl=sh[r+1],hr=ph[l];
    hl.h1*=pw1[r-l+1];
    hl.h1%=MOD;
    hl.h2*=pw2[r-l+1];
    hl.h2%=MOD;
    
    hr.h1-=hl.h1;
    hr.h1+=MOD;
    hr.h1%=MOD;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;

    return hr;
}

bool compare_suffixes(int x, int y) {
    int l1=n-x+1,l2=n-y+1,left=0,right=min(l1,l2),middle;

    if(get_hash(x,x+right-1)==get_hash(y,y+right-1)) return (x>y);

    while(right-left>1) {
        middle=(left+right)>>1;
        if(get_hash(x,x+middle-1)==get_hash(y,y+middle-1)) left=middle;
        else right=middle;
    }

    return (a[x+left]<a[y+left]);
}

void build_suffix_array() {
    for(int i=1;i<=n;i++) sa[i]=i;
    stable_sort(sa+1,sa+1+n,compare_suffixes);
}

void build_lcp() {
    int i,left,right,middle;
    for(i=1;i<n;i++) {
        left=0;
        right=min(n-sa[i]+1,n-sa[i+1]+1)+1;
        while(right-left>1) {
            middle=(left+right)>>1;
            if(get_hash(sa[i],sa[i]+middle-1)==get_hash(sa[i+1],sa[i+1]+middle-1)) left=middle;
            else right=middle;
        }
        lcp[i]=left;
        lcp[i]=min(lcp[i],longest[sa[i]]);
        lcp[i]=min(lcp[i],longest[sa[i+1]]);
    }
}

int main() {
    int tests,current_case;
    int i;
    rolling_hash h;

    pw1[0]=pw2[0]=1;
    for(i=1;i<N;i++) pw1[i]=pw1[i-1]*B1%MOD,pw2[i]=pw2[i-1]*B2%MOD;

    tests=1;
    //scanf("%d", &tests);
    for(current_case=1;current_case<=tests;current_case++) {
        scanf("%s", a+1);
        n=strlen(a+1);

        h.initialize();
        ph[0]=h;
        for(i=1;i<=n;i++) h.append(a[i]),ph[i]=h;

        h.initialize();
        sh[n+1]=h;
        for(i=n;i>=1;i--) h.append(a[i]),sh[i]=h;

        for(i=1;i<=n;i++) {
            int left,right,middle;
            left=0;
            right=min(i-1,n-i+1)+1;
            while(right-left>1) {
                middle=(left+right)>.1;
                if(get_hash(i-middle,i+middle)==get_reversed_hash(i-middle,i+middle)) left=middle;
                else right=middle;
            }
            longest[i-left]=max(longest[i-left],2*left+1);
            if(a[i]==a[i+1] && i<n) {
                left=0;
                right=min(n-i-1,i-1)+1;
                while(right-left>1) {
                    middle=(left+right)>>1;
                    if(get_hash(i-middle,i+1+middle)==get_reversed_hash(i-middle,i+1+middle)) left=middle;
                    else right=middle;
                }
                longest[i-left]=max(longest[i-left],left*2+2);
            }
        }

        for(i=2;i<=n;i++) {
            longest[i]=max(longest[i],longest[i-1]-2);
        }

        build_suffix_array();
        build_lcp();

        while(!s.empty()) s.pop();
        for(i=1;i<n;i++) {
            while(!s.empty() && lcp[s.top()]>=lcp[i]) s.pop();
            if(s.empty()) left[i]=i-1;
            else left[i]=i-s.top()-1;
            s.push(i);
        }

        while(!s.empty()) s.pop();
        for(i=n-1;i>=1;i--) {
            while(!s.empty() && lcp[s.top()]>=lcp[i]) s.pop();
            if(s.empty()) right[i]=n-1-i;
            else right[i]=s.top()-i-1;
            s.push(i);
        }
    
        ans=n;
        for(i=1;i<n;i++) {
            ans=max(ans,(left[i]+right[i]+2)*1ll*lcp[i]);
        }
        
        printf("%lld\n", ans);
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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