Cod sursa(job #2008833)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 7 august 2017 18:51:56
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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;
        }
    }
    int s = 0;
    for(int i = 1; i <= n; i += 2)
    {
        if(p[i] % 2 == 0)
            s = s + p[i] - 1;
        else
            s = s + p[i] + 1;
        if(p[i] == i)
            s--;//, cerr << i << "\n";
        if(p[i] == n - i + 1)
            s--;//, cerr << i << "\n";
    }
    //for(int i = 1; i <= n; i = i + 2)
        //cerr << p[i] << " ";
    out << s << "\n";
    return 0;
}