Cod sursa(job #2910921)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 25 iunie 2022 20:00:35
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

#define N 1000005

using namespace std;

ifstream fin("pscpld.in");

ofstream fout("pscpld.out");



long long ans;

char s[2*N];

vector<int> manacher_odd(char s[]) {

    int n = strlen(s);

    vector<int> p(n + 2);

    int l = 1, r = 1;

    for(int i = 1; i <= n; i++) {

        p[i] = max(0, min(r - i, p[l + (r - i)]));

        while(s[i - p[i]] == s[i + p[i]]) {

            p[i]++;

        }

        if(i + p[i] > r) {

            l = i - p[i], r = i + p[i];

        }

    }

    return p;

}

vector<int> manacher(char s[]) {

    char t[2*N];
	int m=0;
    for(int i=0;s[i];i++) {

        t[m++]='#',t[m++]=s[i];

    }
	t[m++]='#';//cout<<t<<" ";
    auto res = manacher_odd(t);

    return vector<int>(begin(res) + 1, end(res) - 1);

}



int main()

{

    fin>>s;

    vector<int>p=manacher(s);

    for(auto x:p) ans+=x/2;

    fout<<ans;

    return 0;

}