Cod sursa(job #1312494)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 9 ianuarie 2015 16:46:28
Problema PScPld Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 0.97 kb
//algoritmul lui manacher: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
#include <stdio.h>
#define MAXN 1000000
char t[2*MAXN+3];
int p[MAXN+1];
int main(){
    int ans, n, c, r, i, j;
    char ch;
    FILE *fin, *fout;
    fin=fopen("pscpld.in", "r");
    fout=fopen("pscpld.out", "w");
    t[0]='^';
    n=1;
    ch=fgetc(fin);
    while(ch!='\n'){
        t[n++]='#';
        t[n++]=ch;
        ch=fgetc(fin);
    }
    t[n]='#';
    t[n+1]='$';
    ans=0;
    c=0;
    r=0;
    for(i=1; i<=n; i++){
        j=2*c-i;
        if(r>i){
            if(p[j]<=r-i){
                p[i]=p[j];
            }else{
                p[i]=r-i;
            }
        }
        while(t[i+p[i]+1]==t[i-p[i]-1]){
            p[i]++;
        }
        if(i+p[i]>r){
            c=i;
            r=i+p[i];
        }
        ans+=(p[i]+1)/2;
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}