Cod sursa(job #2605830)

Utilizator trifangrobertRobert Trifan trifangrobert Data 25 aprilie 2020 22:25:48
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1000005;
int N, odd[NMAX], even[NMAX];
char s[NMAX];

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    fin >> (s + 1);
    N = strlen(s + 1);
    int l = 1, r = 0, k;
    for (int i = 1;i <= N;++i)
    {
        if (i > r)
            k = 1;
        else
            k = min(odd[l + r - i], r - i + 1);
        while (i - k >= 1 && i + k <= N && s[i - k] == s[i + k])
            ++k;
        odd[i] = k--;
        if (i + k > r)
        {
            r = i + k;
            l = i - k;
        }
    }
    l = 1, r = 0;
    for (int i = 1;i <= N;++i)
    {
        if (i > r)
            k = 0;
        else
            k = min(even[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 1 && i + k <= N && s[i - k - 1] == s[i + k])
            ++k;
        even[i] = k--;
        if (i + k > r)
        {
            r = i + k;
            l = i - k - 1;
        }
    }
    long long answer = 0;
    for (int i = 1;i <= N;++i)
        answer += odd[i] + even[i];
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}