Cod sursa(job #2791256)

Utilizator Robert.BrindeaBrindea Robert Robert.Brindea Data 30 octombrie 2021 11:54:11
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int MAXN = 1000003;

char s[2*MAXN], temp[MAXN];
int n, c, r, p[2*MAXN];

void hashtag()
{
    s[n++] = '#';
    int len = strlen(temp);
    for(int i = 0; i < len; i++)
        s[n++] = temp[i], s[n++] = '#';
}

int main()
{
    fin >> temp;
    hashtag();
    for(int i = 1; i < n; i++)
    {
        int sim = c-(i-c);
        if(i <= r)
            p[i] = min(r-i, p[sim]);
        while(i+p[i]+1 < n && i-p[i]-1 >= 0 && s[i+p[i]+1] == s[i-p[i]-1])
            p[i]++;
        if(i+p[i] > r)
        {
            c = i;
            r = i+p[i];
        }
    }
    long long rez = 0;
    for(int i = 0; i < n; i++)
    {
        rez += p[i]/2;
        if(p[i]%2)rez++;
    }
    fout << rez;
    return 0;
}