Cod sursa(job #2791352)

Utilizator HardtoPronouncePetcu David-Andrei HardtoPronounce Data 30 octombrie 2021 13:25:55
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

const int DIM = 1e6+5;
char v[DIM];
char s[2*DIM];

int builds(int len) {
    int newlen = 0;
    s[0]='#';
    for (int i=0; i<=len; i++)
        s[++newlen] = v[i], s[++newlen] = '#';
    return newlen;
}

int main() {
    f >> v;
    int len = strlen(v)-1;
    len = builds(len);

    vector<int> dis(len+1,0);
    int npal = 0;
    for (int i = 0, r=-1, c=-1; i <= len; i++) {
        if(i>r)
            dis[i]=1;
        else
            dis[i]=min(dis[c-(i-c)],dis[r-i]);
        while (i-dis[i]>=0 && i+dis[i]<=len && s[i-dis[i]]==s[i+dis[i]])
            dis[i]++;
        if (i+dis[i]-1>r)
            r=i+dis[i]-1, c=i;
        npal+=dis[i]/2;
    }
    cout<<npal;
}