Cod sursa(job #1968857)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 17 aprilie 2017 22:07:57
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <cstring>
#define nmax 1000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char a[nmax],s[nmax<<1];
int n,m,c,ans,dp[nmax<<1];

void manacher()
{
    int i,c=0;
    for (i=2;i<=n;i++) {
		dp[i]=1;
		if(c+dp[c]>i)
			dp[i]=min(c+dp[c]-i,dp[2*c-i]);

		dp[i]=max(1,dp[i]);
		while (i-dp[i]>0&&i+dp[i]<=n&&s[i-dp[i]]==s[i+dp[i]])
			++dp[i];

		if (i%2==0)
			ans+=(dp[i])/2;
		else
            ans+=(dp[i]-1)/2;

		if(i+dp[i]>c+dp[c])
			c=i;
	}
}
int main()
{
    int i,j;
	f>>a+1;
	n=strlen(a+1);
	for (i=1,m=0;i<=n;i++) {
		s[++m]='!';
		s[++m]=a[i];
	}
	s[++m]='!';
	n=m;
    manacher();
	g<<ans;
    return 0;
}