Pagini recente » Cod sursa (job #2625051) | Cod sursa (job #1786978) | Cod sursa (job #1280739) | Cod sursa (job #1915629) | Cod sursa (job #1227566)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
#define b1 257
#define M1 10007
#define M2 11003
#define NMAX 1000002
int i, j, N;
int ANS;
char s[NMAX];
int pw1[NMAX];
int pw2[NMAX];
int h1[NMAX];
int h2[NMAX];
int h1_r[NMAX];
int h2_r[NMAX];
inline int BinarySearch(int p, int L, int h, int r) {
int left = 1, right = L, m, k, w, last = 0;
while (left <= right) {
m = (left + right) >> 1;
k = p - m - 1;
w = p + r + m + 1;
if (((h1[p - 1] - (pw1[p - 1 - k] * h1[k]) % M1) + M1) % M1 == ((h1_r[p + 1 + r] - (pw1[w - 1 - (p + r)] * h1_r[w]) % M1) + M1) % M1 &&
((h2[p - 1] - (pw2[p - 1 - k] * h2[k]) % M2) + M2) % M2 == ((h2_r[p + 1 + r] - (pw2[w - 1 - (p + r)] * h2_r[w]) % M2) + M2) % M2) {
last = m;
if (h == 1)
left = m + 1;
else
right = m - 1;
}
else {
if (h == 1)
right = m - 1;
else
left = m + 1;
}
}
return last;
}
int main() {
fin >> (s + 1);
N = strlen(s + 1);
pw1[0] = pw2[0] = 1;
for (i = 1, j = N; i <= N && j >= 1; ++i, --j) {
pw1[i] = (pw1[i - 1] * b1) % M1;
pw2[i] = (pw2[i - 1] * b1) % M2;
h1[i] = (h1[i - 1] * b1 + s[i]) % M1;
h2[i] = (h2[i - 1] * b1 + s[i]) % M2;
h1_r[j] = (h1_r[j + 1] * b1 + s[j]) % M1;
h2_r[j] = (h2_r[j + 1] * b1 + s[j]) % M2;
}
int top, bot;
for (i = 1; i < N; ++i)
if (s[i] == s[i + 1]) ++ANS;
for (i = 2; i < N; ++i) {
top = BinarySearch(i, min(i - 1, N - i), 1, 0);
bot = BinarySearch(i, min(i - 1, N - i), 0, 0);
if (top && bot)
ANS += (top - bot + 1);
if (s[i] == s[i + 1]) {
top = BinarySearch(i, min(i - 1, N - (i + 1)), 1, 1);
bot = BinarySearch(i, min(i - 1, N - (i + 1)), 0, 1);
if (top && bot)
ANS += (top - bot + 1);
}
}
fout << ANS + N << '\n';
return 0;
}