Pagini recente » Cod sursa (job #496070) | Cod sursa (job #1121239) | Cod sursa (job #1902641) | Cod sursa (job #2382431) | Cod sursa (job #752845)
Cod sursa(job #752845)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
#define N 2000001
char b[1000001], a[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(b, 1000001);
n = strlen(b);
for(i = 0; i!=n; ++i) {
a[2*i + 1] = b[i];
a[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] > 0 && a[i - p[i]] == a[i + p[i]])
++p[i];
if(i & 1)
nr += (p[i] + 1)>>1;
else
nr += p[i]>>1;
if(p[i] + i > poz + l) {
poz = i;
l = p[i];
}
}
out << nr << "\n";
return 0;
}