Cod sursa(job #842263)

Utilizator mihai995mihai995 mihai995 Data 26 decembrie 2012 15:57:13
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N = 1000005;
int P[N];
char s[N];

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

long long pali(char s[], bool d){
    int best = 0;
    long long rez = 0;
    memset(P, 0, sizeof(P));

    char *a = s, *b = s + 1 - d;

    for (int i = 1 ; s[i] ; i++){
        if (i < best + P[best])
            P[i] = min(best + P[best] - i, P[2 * best - i]);

        while (P[i] < i && b[ i + P[i]] && a[i - P[i]] == b[i + P[i]])
            P[i]++;

        if (i + P[i] > best + P[best])
            best = i;

        rez += P[i];
    }

    return rez;
}

int main(){
    in >> (s + 1);

    out << pali(s, 0) + pali(s, 1) << "\n";

    return 0;
}