Cod sursa(job #1693451)

Utilizator sucureiSucureiRobert sucurei Data 23 aprilie 2016 09:45:45
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1000002

using namespace std;

int n, i, j, pos, a;
long long sol;
int len[maxN * 2];
char s[maxN * 2], S[maxN];
void read()
{
    freopen("pscpld.in", "r", stdin);
    gets(S + 1);
    n=strlen(S + 1);
    s[0]='*';
    for (i=1;i<=n;++i)
    {
        s[(i-1)*2+1]=S[i];
        s[i*2]='*';
    }
    n*=2;
}
void solve()
{
    pos=0;
    a=0;
    sol=0;
    for (i=1;i<=n;++i)
    {
        if (i<=pos)
            len[i]=min(len[2*a-i],(pos - i));
        while (i-len[i]-1>=0 && i+len[i]+1<=n && s[i-len[i]-1]==s[i+len[i]+1])
            ++len[i];
        if (i+len[i]>pos)
        {
            pos=i+len[i];
            a=i;
        }
        sol=(long long)(sol+(len[i]+1)/2)*1LL;
    }
}
void write()
{
    freopen("pscpld.out","w",stdout);
    printf("%lld\n",sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}