Cod sursa(job #2376228)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 8 martie 2019 14:19:08
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>

const int MAXN = 1000000 * 2 + 5;

using namespace std;

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

int p[MAXN];

int main()
{
    string input,s;
    in>>input;
    s += '$';
    for(int i = 0; i < input.size(); i++){
        s += '#';
        s += input[i];
    }
    s += '#';
    s += '$';
    int center = 0,right = 0;
    for(int i = 1; i < s.size(); i++){
        int mirror = 2 * center - i;
        if(i < right)
            p[i] = min(p[mirror],right - i);
        while(s[i + p[i] + 1] == s[i - p[i] - 1])
            p[i]++;
        if(i + p[i] > right){
            right = i + p[i];
            center = i;
        }
    }
    long long ans = 0;
    for(int i = 0; i < s.size(); i++)
        ans += p[i] / 2 + (p[i] % 2 != 0);
    out<<ans<<"\n";;
    return 0;
}