Cod sursa(job #2336700)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 5 februarie 2019 14:16:28
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char a[1000010];
char s[2000010];
int p[2000010];
int n;
void addHash(){
    n=strlen(a);
    for(int i=0; i<n; i++)
    {
        s[2*i]='#';
        s[2*i+1]=a[i];
    }
    s[2*n]='#';

}
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",a);
    addHash();
    int simi, C=0, R=0;
    int m=2*n;
    long long vmax=0;
    for(int i=0; i<=m; i++)
    {
        simi=C-(i-C);
        if(i<=R)
            p[i]=min(p[simi],R-i);
        while(s[i+1+p[i]]==s[i-1-p[i]] && i+1+p[i]<=m && i-1-p[i]>=0)
            p[i]++;
        if(i+p[i]>=R)
        {
            C=i;
            R=i+p[i];
        }
        vmax=vmax+1LL*(p[i]+1)/2;
    }
    printf("%lld",vmax);
    return 0;
}