Pagini recente » Cod sursa (job #124338) | Cod sursa (job #3321997) | Cod sursa (job #699607) | Cod sursa (job #3313352) | Cod sursa (job #1889302)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream re ("pscpld.in");
ofstream we ("pscpld.out");
const int MAXN = 1000005;
char s[2 * MAXN];
int p[2 * MAXN], n;
int main ()
{
re >> s;
n = strlen(s);
long long sum = n;
for(int i = n - 1; i >= 0; i--) {
s[i * 2 + 1] = s[i];
s[i * 2 + 2] = '#';
}
s[0] = '#';
n = n * 2;
int r = 0;
int m = 0;
p[0] = 0;
p[n] = 0;
for(int i = 1; i < n; i++) {
int j;
//cout << " m = " << m << " r = " << r << " i = " << i << " j = " << j << ' ';
if(i < r) {
j = 2 * m - i;
//cout << " jiji:" << j;
if(j >= 0 && i + p[j] < r) {
p[i] = p[j];
//cout << " CAZ 1";
} else {
j = r - i;
int aux = 2 * m - r;
//cout << " gaf:" << aux;
while((i + j <= n) && (i - j >= 0) && (s[i + j] == s[i - j])) {
j++; //cout << " BAU:" << j;
}
j--;
m = i;
r = i + j;
p[i] = j;
//cout << " CAZ 2";
}
} else {
j = 0;
while(i + j <= n && i - j >= 0 && s[i + j] == s[i - j]) {
j++;
}
j--;
m = i;
r = i + j;
p[i] = j;
////cout << " CAZ 3";
}
////cout << endl;
sum += p[i] / 2;
}
/*
for(int i = 0; i <= n; i++) {
we << s[i] << ' ';
}
we << endl;
for(int i = 0; i <= n; i++) {
we << p[i] << ' ';
}
*/
we << sum;
re.close();
we.close();
return 0;
}