Cod sursa(job #3226793)

Utilizator Darius1414Dobre Darius Adrian Darius1414 Data 22 aprilie 2024 20:23:50
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
using namespace std;
string s2,s;
int v[2000005];
int main()
{
    ifstream f ("pscpld.in");
    ofstream g ("pscpld.out");
    f>>s2;
    s+='$';
    for (int i=0; i<s2.size(); i++)
    {
        s+='#';
        s+=s2[i];
    }
    s+='#';
    s+='@';
    int sz=s.size();
    int center=0,right=0,mirror;
    for (int i=1; i<sz; i++)
    {
        int mirror=center*2-i;
        if (i<right)
            v[i]=min(v[mirror],right-i);
        while (s[i+1+v[i]]==s[i-(1+v[i])])
            v[i]++;
        if (i+v[i]>right)
        {
            center=i;
            right=i+v[i];
        }
    }
    int ct=0;
    for (int i=0; i<sz; i++)
        if (v[i])
            ct+=(v[i]-1)/2+1;
    g<<ct;
}