Cod sursa(job #1013086)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 20 octombrie 2013 11:24:40
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <string.h>
#define Nmax 1000099
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");

int N,P[2*Nmax],C,R;
char S[Nmax],T[2*Nmax];
unsigned long long sol;
inline void ReadInput()
{
    f.getline(S+1,Nmax,'\n');
    N=strlen(S+1);
}
inline void Preprocess()
{
    //din "abba" fac "^#a#b#b#a#$"
    T[0]='^';T[1]='#';
    for(int i=1;i<=N;++i)T[2*i]=S[i],T[2*i+1]='#';
    T[2*N+2]='$';
    N*=2;
}

inline int FindLPS(char T[])
{
    for(int i=1;i<=N;++i)
    {
        int i_mirror=2*C-i;
        if(R>i)P[i]=min(R-i,P[i_mirror]);
            else P[i]=0;
        while(T[i+1+P[i]] == T[i-1-P[i]])++P[i];
        if(i+P[i]>R)
        {
            C=i;
            R=i+P[i];
        }
    }
}

inline void PrintLPS()
{
    for(int i=1;i<=N;++i)
        if(P[i])
        {
            if(P[i]%2==0)sol+=P[i]/2;
            else sol+=P[i]/2+1;
        }
    g<<sol<<'\n';
}
int main()
{
    ReadInput();
    Preprocess();
    FindLPS(T);
    PrintLPS();
    f.close();g.close();
    return 0;
}