Pagini recente » Cod sursa (job #124466) | Cod sursa (job #1683977) | Cod sursa (job #1587076) | Cod sursa (job #1030767) | Cod sursa (job #2843567)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
char s[2000055],s2[2000055];
int st,dr,n,z[1000055],i,ma;
int main()
{
in.getline(s,1000035);
st=dr=0;
n=strlen(s);
for (i=0;i<n;++i)
{
s2[2*i+1]=s[i];
s2[2*i]='#';
}
s2[2*n]='#';
n=2*n+1;
for (i=0;i<n;++i)
s[i]=s2[i];
z[0]=0;
for (int i=1;i<n;++i)
{
if (dr<i) {while (i+z[i]<n-1&&i>z[i]&&s[i+z[i]+1]==s[i-z[i]-1]) {z[i]++;} st=i-z[i]; dr=i+z[i];}
else if (dr>=i&&dr<=i+z[(dr-i)+st]) {z[i]=dr-i; while (i+z[i]<n-1&&i>z[i]&&s[i+z[i]+1]==s[i-z[i]-1]) z[i]++; st=i-z[i]; dr=i+z[i];}
else {z[i]=z[(dr-i)+st];}
ma+=((z[i]+1)/2);
}
out<<ma;
return 0;
}