Cod sursa(job #3041412)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 31 martie 2023 14:14:36
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
///aceasta problema este implementata pt a repeta manacher
///nu inteleg de ce are 5 stele, trebuia sa fie de 2

#include <fstream>
#include <string>

using namespace std;

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

const int N = 2e6 + 10;
int m[N + 1];

string s;

int main()
{
    cin >> s;
    string aux;
    aux += '@';
    for (auto it : s)
        aux += it, aux += '@';
    s = aux;
    for (int i = 0, l = 0, r = 0; i < s.size(); ++i)
    {
        if (i <= r)
            m[i] = min (m[l + r - i], r - i + 1);
        while (i + m[i] < s.size() && s[i + m[i]] == s[i - m[i]])++m[i];
        if (i + m[i] - 1 > r)
            r = i + m[i] - 1, l = i - m[i] + 1;
    }
    long long rez = 0;
    for (int i = 0; i < s.size(); ++i)
    {
      //  cout << m[i] << ' ';
        rez += (m[i] >> 1);
    }
    cout << rez << '\n';
    return 0;
}