Cod sursa(job #2553149)

Utilizator trifangrobertRobert Trifan trifangrobert Data 21 februarie 2020 18:00:13
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 20000005;
int palin[NMAX], N;
char t[NMAX], s[NMAX];

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    fin >> (t + 1);
    N = strlen(t + 1);
    for (int i = 1;t[i];++i)
    {
        s[2 * i - 1] = '*';
        s[2 * i] = t[i];
        ++N;
    }
    s[++N] = '*';
    int left = 0, right = -1;
    for (int i = 1;i <= N;++i)
    {
        int k;
        if (i > right)
        {
            k = 1;
            while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
                ++k;
        }
        else
        {
            k = palin[left + right - i];
            if (i + k - 1 < right)
                palin[i] = k;
            else
            {
                k = right - i + 1;
                while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
                    ++k;
            }
        }
        palin[i] = k;
        if (i + k - 1 > right)
        {
            right = i + k - 1;
            left = i - k + 1;
        }
    }
    long long answer = 0;
    for (int i = 1;i <= N;++i)
        answer += (palin[i] / 2);
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}