Cod sursa(job #1678310)

Utilizator GinguIonutGinguIonut GinguIonut Data 7 aprilie 2016 10:35:54
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <string.h>

#define nMax 2000008
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n;
int dp[nMax];
char S[nMax], sir[nMax];
void read()
{
    fin>>S+1;

    for(int i=1;S[i]!=0;i++)
    {
        sir[++n]='#';
        sir[++n]=S[i];
    }
    sir[++n]='#';
}
void solve()
{
    int C=0, R=0;
    for(int i=1;i<=n;i++)
    {
        if(i<=R)
            dp[i]=min(dp[C-(i-C)], R-i+1);
        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;
        }
    }
}
void write()
{
    long long Sol=0;
    for(int i=1;i<=n;i++)
        Sol+=dp[i]/2;

    fout<<Sol;
}
int main()
{
    read();
    solve();
    write();
    return 0;
}