Cod sursa(job #1880258)

Utilizator stefanchistefan chiper stefanchi Data 15 februarie 2017 17:25:43
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstring>
#define Cmax 1000002
using namespace std;
char sentence[Cmax];
int lps[2*Cmax + 1],c,r,dif;
long long nr;
void read()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",&sentence);
}

void manacher()
{
    lps[0]= 0;
    lps[1]= 1;
    c = 1;
    r = 2;
    int lung = strlen(sentence);
    int simetric;
    lung = lung * 2 + 1;
    for(int i = 2 ; i < lung; i++)
    {
        dif = r - i;
        simetric = 2*c-i;
        if(i < r)
         {
             if( lps[simetric] < dif)
                lps[i] = lps[simetric];
             else
                lps[i] = dif;
         }
        else
            lps[i] = 0;
        while((i - lps[i]-1 >= 0  && i + lps[i] + 1 <= lung) && ((sentence[(i-lps[i]-1)/2] == sentence[(i + lps[i]+1)/2]) || ((1+lps[i]+i)%2 == 0 )))
            lps[i]++;
        if(lps[i] + i > r)
        {
            c = i;
            r = i + lps[i];
        }
    }
    for(int i = 1 ; i < lung - 1 ; i++)
            if(lps[i] % 2 == 0)
                nr+= lps[i] / 2;
            else
                nr+= lps[i]/2 + 1;
}

int main()
{
    read();
    manacher();
    printf("%lld",nr);
    return 0;
}