Cod sursa(job #2590793)

Utilizator vladth11Vlad Haivas vladth11 Data 28 martie 2020 22:04:51
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;
typedef long long ll;

int p[2000005];

ll Manacher(string s)
{
    ll rez = 0;

    int l = 0,r = -1;
    for(int i = 0; i < s.size(); i++)
    {
        int k = 0;
        if(i > r)
        {
            k = 1;
        }
        else
        {
            k = min(p[r - i + l], r - i + 1);
        }
        while(i - k >= 0 && i + k < s.size() && s[i - k] == s[i + k])
            k++;
        if(s[i - k] != s[i + k])
        {
            k--;
        }
        p[i] = k;
        if(i + p[i] > r)
        {
            r = i + p[i];
            l = i - p[i];
        }
    }
    for(int i = 0; i < s.size(); i++)
    {
        rez += (p[i] + 1) / 2;
    }
    return rez;
}

int main()
{
    int i;
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    string a,s = "";
    cin >> a;
    s += "#";
    for(i = 0; i < a.size(); i++)
    {
        s += a[i];
        s += "#";
    }
    cout << Manacher(s);
    return 0;
}