Cod sursa(job #834376)

Utilizator DraStiKDragos Oprica DraStiK Data 14 decembrie 2012 11:34:35
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int NMAX=2000005;

char S[NMAX],T[NMAX];
int best[NMAX];
long long ret;
int N,M;

void read () {
    fgets (S,NMAX,stdin);
    N=strlen (S)-(S[strlen (S)-1]=='\n');

    T[++M]='#';
    for (int i=0; i<N; ++i) {
		T[++M]=' ';
		T[++M]=S[i];
    }
	T[++M]=' '; T[++M]='$';
}

void solve () {
	int C,R;

    C=R=0;
	for (int i=1; i<M; ++i) {
		int mirror_i=2*C-i;

		if (i<R)
			best[i]=min (R-i,best[mirror_i]);

		while (T[i-best[i]-1]==T[i+best[i]+1])
			++best[i];

		if (i+best[i]>R) {
			C=i;
			R=i+best[i];
		}

		ret+=(best[i]+1)/2;
	}

	cout<<ret;
}

int main () {
    freopen ("pscpld.in","r",stdin);
    freopen ("pscpld.out","w",stdout);

    read ();
    solve ();

    return 0;
}