Cod sursa(job #2836105)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 19 ianuarie 2022 19:18:30
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

string a;
int s[2000005];

int main()
{
    char ch;
    while (in >> ch)
    {
        a.push_back('*');
        a.push_back(ch);
    }
    int l = 0,r = 0;
    for (int i = 1; i < a.size(); i++)
    {
        if (i > r)
        {
            int p1 = i - 1,p2 = i + 1;
            while (p1 >= 0 and p2 <= a.size() and a[p1] == a[p2])
            {
                s[i]++;
                p1--;
                p2++;
            }
            l = i - s[i];
            r = i + s[i];
        }
        else
        {
            int c = (r + l) / 2;
            int d = i - c;
            int pi = c - d;
            if (s[pi] < pi - l)
                s[i] = s[pi];
            else
            {
                s[i] = r - i;
                int p1 = 2 * i - r - 1,p2 = r + 1;
                while (p1 >= 0 and p2 <= a.size() and a[p1] == a[p2])
                {
                    s[i]++;
                    p1--;
                    p2++;
                }
                r = i + s[i];
                l = i - s[i];
            }
        }
    }
    long long sum = 0;
    for (int i = 1; i <= a.size(); i++)
        sum += s[i] / 2;
    sum += a.size() / 2;
    out << sum;
    return 0;
}