Cod sursa(job #1923155)

Utilizator GinguIonutGinguIonut GinguIonut Data 10 martie 2017 21:03:51
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <string.h>

#define nMax 1000005

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char S[nMax], sir[2*nMax];
int n, dp[2*nMax];

int main()
{
    fin>>S+1;
    for(int i=1; S[i]!=0; i++)
    {
        sir[++n]='#';
        sir[++n]=S[i];
    }
    sir[++n]='#';

    long long Sol=0;
    int C=0, R=0;
    for(int i=1; i<=n; i++)
    {
        if(i<=R)
            dp[i]=min(R-i+1, dp[C-(i-C)]);
        while(sir[i+dp[i]]==sir[i-dp[i]] && i+dp[i]<=n && i-dp[i]>=1)
            dp[i]++;
        if(i+dp[i]-1>R)
        {
            R=i+dp[i]-1;
            C=i;
        }
        Sol+=dp[i]/2;
    }

    fout<<Sol;

}