Pagini recente » Cod sursa (job #174846) | Arhiva de probleme | Diferente pentru implica-te/arhiva-educationala intre reviziile 58 si 57 | Cod sursa (job #3041556) | Cod sursa (job #752840)
Cod sursa(job #752840)
#include<cstdio>
#include<cstring>
char b[1000001],a[2000001];
int n,i,lg=1,poz=1,s[2000001];
long long nr;
int m(int a,int b)
{
if(a<b) return a;
return b;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(b);
s[0]=1;
n=strlen(b);
for(i=0;i<n;i++){
a[2*i+1]=b[i];
a[2*i]=' ';}
n=2*n-1;
s[1]=1;
nr=1;
for(i=2;i<=n;i++){
s[i]=1;
if(poz+lg-1>i)
s[i]=m(poz+lg-i,s[2*poz-i]);
while(i-s[i]>0 && a[i-s[i]]==a[i+s[i]]) s[i]++;
if(i%2)
nr+=(s[i]+1)/2;
else
nr+=s[i]/2;
if(s[i]+i>poz+lg) poz=i,lg=s[i];}
printf("%lld\n",nr);
fclose(stdout);
return 0;
}
/*#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int N = 2000100;
char a[N], s[N];
int p[N], n, poz = 1, l = 1;
long long nr = 1;
inline int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int i;
in.getline(a, N);
n = strlen(a);
for(i = 0; i!=n; ++i) {
s[2*i + 1] = a[i];
s[2*i] = ' ';
}
n = 2*n - 1;
p[0] = p[1] = 1;
for(i = 2; i<=n; ++i) {
p[i] = 1;
if(poz + l - 1 > i)
p[i] = min(poz + l - i, p[2 * poz - i]);
while(i - p[i] && s[i - p[i]] == s[i + p[i]])
++p[i];
if(i & 1)
nr += (p[i] + 1)>>1;
else
nr += p[i]>>1;
if(s[i] + i > poz + l) {
poz = i;
l = p[i];
}
}
out << nr << "\n";
return 0;
}*/