Cod sursa(job #1880209)

Utilizator stefanchistefan chiper stefanchi Data 15 februarie 2017 16:56:13
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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("pscpldc.in","r",stdin);
    freopen("pscpldc.out","w",stdout);
    scanf("%s",&sentence);
}

void manacher()
{
    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((sentence[i - lps[i]-1] >= 0  && sentence[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 = lps[i];
        }
    }
    for(int i = 1 ; i < lung - 1 ; i++)
        if(lps[i] != 0)
           nr += lps[i];
}

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