Cod sursa(job #2008638)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 7 august 2017 03:41:34
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 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)
        s = s + p[i];
    out << s - n1 / 2 << "\n";
    return 0;
}