Cod sursa(job #1980960)

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