Pagini recente » Cod sursa (job #1419833) | Cod sursa (job #176896) | Cod sursa (job #109130) | Cod sursa (job #1164752) | Cod sursa (job #3224430)
//https://www.infoarena.ro/problema/pscpld
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int d[1000000];
int main()
{
int ex=0,rez=1,i,ssize;
string s;
fin>>s;
ssize=s.size();
ssize=ssize*2-1;
d[0]=1;
for(i=1;i<ssize;++i)
{
if(i<ex+d[ex])//daca este mai mic decat ex
{
d[i]=min(d[ex*2-i],d[ex]+ex-i);
}
else//alfel
{
if(i&1)
{
d[i]=0;
}
else
{
d[i]=1;
}
}
while((i+d[i]<ssize-1)&&(i-d[i]>0))//ma duc in dreapra si stinga sa vad daca ma mai pot duce
{
if(s[(i+d[i]+1)/2]!=s[(i-d[i]-1)/2])//daca sunt diferite
{
break;
}
d[i]+=2;
}
rez+=(d[i]+1)/2;//pun rezultatul
if(i+d[i]>ex+d[ex])//daca este mai mare pun ex
{
ex=i;
}
}
fout<<rez;
return 0;
}