Cod sursa(job #1534274)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 noiembrie 2015 16:59:54
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

const int NMAX=2000005;

int n,man[NMAX];
long long sol;
char s[NMAX],t[NMAX];

void Manacher()
{
    int i,C,R,mirror;
    C=R=1;
    for (i=2;i<=n;i++)
    {
        mirror=i-2*(i-C);

        if (i<=R) man[i]=min(man[mirror],R-i);

        while (s[i+man[i]+1]==s[i-man[i]-1]) man[i]++;

        if ((i+man[i])>R)
        {
            C=i;
            R=i+man[i];
        }
    }
}

int main()
{
    int i;
    fin>>(t+1);
    n=strlen(t+1);sol=n;
    for (i=1;i<=n;i++)
        {
            s[2*i-1]='#';
            s[2*i]=t[i];
        }
    n<<=1;
    s[0]='@';s[n+1]='$';
    Manacher();
    for (i=1;i<=n;i++)
        sol+=man[i]>>1;
    fout<<sol<<"\n";
    return 0;
}