Pagini recente » Cod sursa (job #1369008) | Cod sursa (job #937158) | Cod sursa (job #1945631) | Cod sursa (job #2942493) | Cod sursa (job #2795415)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char sh[1000005],s[2000010];
int p;
int P[2000010];
void addH(){
int l=strlen(sh),j=0;
for(int i=0;i<l;i++){
s[j++]='#';
s[j++]=sh[i];
}
s[j++]='#';
s[j]=0;
p=j;
}
int main()
{
f.getline(sh,1000005);
addH();
int R=0,C=0,si=0;
for(int i=1;i<p;i++){
si=C-(i-C);
if(i<=R) P[i]=min(R-i,P[si]);
while(i+1+P[i]<p && i-1-P[i]>=0 && s[i+1+P[i]]==s[i-1-P[i]]){
P[i]++;
}
if(i+P[i]>R){
R=i+P[i];
C=i;
}
}
long long h=0;
for(int i=0;i<p;i++)
h=h+P[i]/2+P[i]%2;
g<<h;
}