Pagini recente » Cod sursa (job #1737061) | Cod sursa (job #1682388) | Cod sursa (job #5435) | Cod sursa (job #1007105) | Cod sursa (job #2967470)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int nmax = 1e6;
long long Manacher(string str) {
int n = str.length();
if (n == 0)
return -1;
n = 2 * n + 1;
int L[nmax + 1];
L[0] = 0, L[1] = 1;
int center = 1, center_right = 2, curr_right = 2;
int curr_left, len, diff;
bool expand;
for (curr_right = 2; curr_right < n; curr_right++) {
curr_left = 2 * center - curr_right;
diff = center_right - curr_right;
expand = 0;
if (diff >= 0) {
//case 1
if (L[curr_left] < diff) {
L[curr_right] = L[curr_left];
}
//case 2
else if (L[curr_left] == diff && curr_right == n - 1) {
L[curr_right] = L[curr_left];
}
//case 3
else if (L[curr_left] == diff && curr_right < n - 1) {
L[curr_right] = L[curr_left];
expand = 1;
}
//case 4
else if (L[curr_left] > diff) {
L[curr_right] = diff;
expand = 1;
}
}
else {
L[curr_right] = 0;
expand = 1;
}
if (expand) {
while (((curr_right + L[curr_right]) < n && (curr_right - L[curr_right] > 0))
&& (((curr_right + L[curr_right] + 1) % 2 == 0)
|| (str[(curr_right + L[curr_right] + 1) / 2] == str[(curr_right - L[curr_right] - 1) / 2]))) {
L[curr_right]++;
}
}
if (curr_right + L[curr_right] > center_right) {
center = curr_right;
center_right= curr_right + L[curr_right];
}
}
long long ans = (n - 1) / 2;
for (int i = 0; i < n; i++) {
if (L[i] > 1) {
ans += L[i] / 2;
}
}
return ans;
}
int main() {
string str;
cin >> str;
cout << Manacher(str);
}