Cod sursa(job #2798636)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 11 noiembrie 2021 17:21:32
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

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

string temp, s;
int v[2000005];
long long ans;

int main()
{
    ios::sync_with_stdio(false);
    fin >> temp;
    int len = temp.size();
    s = '$';
    for(int i = 1; i <= len; i++)
    {
        s += temp [i - 1];
        s += '$';
    }
    len *= 2;
    int poz = 0, dr = 0;
    for(int i = 1; i < len; i++)
    {
        int sim = 2 * poz - i;
        if(dr > i)
            v[i] = min(dr - i, v[sim]);
        while((i >= v[i] + 1) && (i + v[i] + 1 <= len) && s[i + v[i] + 1] == s[i - 1 - v[i]])
            v[i]++;
        if(i + v[i] > dr)
        {
            poz = i;
            dr = i + v[i];
        }
        if(i % 2 == 1)
            ans += (v[i] + 1) / 2;
        else
            ans += v[i] / 2;
    }
    fout << ans;
    return 0;
}