Pagini recente » Cod sursa (job #407606) | Cod sursa (job #2676237) | Cod sursa (job #2676234) | Cod sursa (job #1043767) | Cod sursa (job #919029)
Cod sursa(job #919029)
#include<fstream>
#include<cstring>
#define NMAX 1000005
#define min(a,b) a<b?a:b
using namespace std;
char x[NMAX];
int n,m,DP[NMAX];
long long sol;
void read()
{
ifstream fin("pscpld.in");
fin>>x+1;
x[0]=' ';
n=strlen(x)-1;
fin.close();
}
int expand(int left,int right)
{
int L=0;
for(;left && right<=n & x[left]==x[right];left--,right++)
L++;
return L;
}
void manacher(int par)
{
int p=0,r=0,left,right;
memset(DP,0,4*(n+2));
for(int i=1;i<=n;i++)
{
if(par && x[i]!=x[i+1])
continue;
if(r>=i+par)
DP[i]=min(DP[p-(i-p)],r-i-par);
left=i-DP[i];
right=i+DP[i]+par;
DP[i]+=expand(left,right);
if(i+DP[i]+par>r)
{
r=i+DP[i]+par;
p=i;
}
sol+=DP[i];
}
}
void print()
{
ofstream fout("pscpld.out");
fout<<sol<<'\n';
fout.close();
}
int main()
{
read();
manacher(0);
manacher(1);
print();
return 0;
}