Cod sursa(job #2040957)

Utilizator ilucianIlea Lucian ilucian Data 16 octombrie 2017 18:54:26
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
char T[1000002];
char S[2000005];
int  P[2000005];
int id,mx;
int n,m;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
long long rez;
int main()
{
    fi>>T+1;
    n=strlen(T+1);
    for (int i=1;i<=n;i++)
        S[2*i]=T[i];
    for (int i=1;i<=2*n;i=i+2)
        S[i]='*';
    S[0]='+';
    S[2*n+1]='*';
    S[2*n+2]='-';
    S[2*n+3]='\0';
    m=2*n+1;
    id=1;
    mx=1;
    P[1]=1;
    for (int i=2;i<=m;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;
        }
    }
    /*
    for (int i=1;i<=m;i++)
        cout<<S[i];
    cout<<"\n";
    for (int i=1;i<=m;i++)
        if (i%2==1)
            cout<<(P[i]-1)/2;
        else
            cout<<P[i]/2;
    */
    rez=0LL;
    for (int i=1;i<=m;i++)
        if (i%2==1)
            rez=rez+(P[i]-1)/2;
        else
            rez=rez+P[i]/2;
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}