Cod sursa(job #2041231)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 16 octombrie 2017 22:56:30
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#define VAL 2000005

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int N, i, j, mx;
int P[VAL], id;
long long ANS;
string s, S;

int main()
{
    fin >> s;
    N=2*s.size()+1;
    S+='+';
    S+='*';
    for (i=0; i<s.size(); i++)
    {
        S+=s[i];
        S+='*';
    }
    S+='-';
    P[1]=1;
    id=mx=1;
    for (i=2; i<=N; i++)
    {
        if (i<=mx)
          P[i]=min(P[2*id-i], mx-i);
        else
          P[i]=1;
        while (S[i+P[i]]==S[i-P[i]])
          P[i]++;
        if (i+P[i]-1>mx)
        {
            id=i;
            mx=i+P[i]-1;
        }
        if (i % 2==0)
          ANS+=P[i] / 2;
        else
          ANS+=(P[i]-1) / 2;
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}