Cod sursa(job #2008956)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 8 august 2017 03:11:59
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int maxn = 2000005;
char aux[maxn * 2];
char T[maxn];
int p[maxn];
int rez;

int main()
{
    in.getline(aux + 1, maxn);
    int n1 = strlen(aux + 1);
    int n = 0;
    for(int i = 1; i <= n1; i++)
    {
        T[++n] = aux[i];
        T[++n] = '#';
    }
    T[0] = '?';
    T[n] = '!';
    n--;
    int st = 0;
    int dr = 0;
    for(int i = 1; i <= n; i++)
    {
        if(i <= dr)
            p[i] = min(p[st + dr - i], dr - i + 1);
        else
            p[i] = 1;
        while(T[i - p[i]] == T[i + p[i]])
            p[i]++;
        if(i + p[i] - 1 > dr)
        {
            st = i - p[i] + 1;
            dr = i + p[i] - 1;
        }
    }
    long long s = 0;
    for(int i = 1; i <= n; i++)
    {
        if(isalpha(T[i]))
        {
            if(p[i] % 2 == 0)
                s = s + p[i] / 2;
            else
                s = s + (p[i] + 1) / 2;
        }
        else
            s = s + p[i] / 2;
    }
    //for(int i = 1; i <= n; i++)
        //cerr << p[i] << " ";
    out << s << "\n";
    return 0;
}