Pagini recente » Cod sursa (job #692753) | Cod sursa (job #1283376) | Cod sursa (job #929540)
Cod sursa(job #929540)
#include <fstream>
using namespace std;
const int N=1000100;
char s[N],t[N];
int p[2*N+3];
int k;
long long rez;
void citire()
{
ifstream f("pscpld.in");
f.get(s,N);
f.close();
}
void preproc()
{
t[0]='$';
for(int i=0;s[i]!='\0';++i)
t[++k]='#',t[++k]=s[i];
t[++k]='#';
t[++k]='^';
}
void solve()
{
int c=0,r=0; //centru si limita dreapta
for(int i=1;i<k-1;++i)
{
int i_sim=2*c-i; //simetric fata de centru
p[i]=(r>i)?min(r-i,p[i_sim]):0;
while(t[i+p[i]+1]==t[i-p[i]-1])
p[i]++;
if(i+p[i]>r)
{
c=i;
r=i+p[i];
}
rez+=((p[i]+1)/2);
}
}
void afisare()
{
ofstream h("pscpld.out");
h<<rez;
h.close();
}
int main()
{
citire();
preproc();
solve();
afisare();
return 0;
}