Cod sursa(job #931396)

Utilizator ELHoriaHoria Cretescu ELHoria Data 28 martie 2013 10:51:16
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

const int NMAX = int(1e6) + 5;
char s[NMAX], *ss;
int p[NMAX*2 + 2];

int main()
{
	cin.getline(s,32);
	int n = strlen(s);
	ss = new char[n*2 + 2];
	int nn = 2*n+2;
    ss[0] = '$', ss[nn-1] = '#', ss[nn] = 0;
    for(int i = 0;i < n;i++) ss[i*2+1] ='#', ss[i*2+2] = s[i];
    int mx = 0, id = 0; 
	for(int i = 1;i <= nn;i++){
        p[i] = mx > i ? min(p[2*id-i], mx - i) : 1;
        while (ss[i+p[i]] == ss[i-p[i]]) p[i]++;
        if (i + p[i] > mx) mx = i + p[i], id = i;
    }
	long long ans = 0;
	for(int i = 1; i <= 2*n;i++) {
		ans += p[i]>>1;
	}
	cout<<ans;
	return 0;
}