Cod sursa(job #1980913)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 mai 2017 13:11:42
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
/**
    Manacher Algorithm: O(n) time
*/
#include<bits/stdc++.h>
#define maxN 1000005
using namespace std;
int n,k,odd[maxN],sol,even[maxN];
char s[maxN];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    int l=0,r=-1;
    for(int i=1;i<=n;i++)
    {
        if(i>r)
        {
            k=1;
        }
            else k=min(odd[l+r-i],r-i)+1;
        while((i+k)<=n && (i-k)>0 && s[i+k]==s[i-k]) k++;
        odd[i]=k--;
        if((i+k)>r)
        {
            r=i+k;
            l=i-k;
        }
    }
    l=0;
    r=-1;
    for(int i=1;i<=n;i++)
    {
        if(i>r) k=1;
            else
        k=min(even[l+r-i-1],r-i+1)+1;
        while((i+k-1)<=n && (i-k)>=1 && s[i+k-1]==s[i-k]) k++;
        k--;
        even[i]=k;
        if((i+k-1)>r)
        {
            l=i-k;
            r=i+k-1;
        }
    }
    for(int i=1;i<=n;i++)
        sol=sol+odd[i]+even[i];
    printf("%d\n",sol);
    return 0;
}