Pagini recente » Cod sursa (job #2455033) | Cod sursa (job #1410798) | Cod sursa (job #2796114) | Cod sursa (job #2328636) | Cod sursa (job #1097507)
#include <string>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int N = 2e6 + 5;
string Input, s;
int Len[2][N], n;
long long sol;
int expand(int st, int dr) {
int sol = 0;
while (st && dr <= n && s[st] == s[dr])
st--, dr++, sol++;
return sol;
}
void Manacher_Odd() {
int best = 0, poz = 0;
for (int i = 1; i <= n; ++i) {
if (best >= i)
Len[0][i] = min(Len[0][2 * poz - i], best - i);
int st = i - Len[0][i], dr = i + Len[0][i];
Len[0][i] += expand(st, dr);
if (i + Len[0][i] > best) {
best = Len[0][i] + i;
poz = i;
}
sol += 1LL * Len[0][i];
}
}
void Manacher_Even() {
int best = 0, poz = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] != s[i+1])
continue;
if (best >= i)
Len[1][i] = min(Len[1][2 * poz - i], best - i - 1);
int st = i + Len[1][i], dr = i + 1 + Len[1][i];
Len[1][i] += expand(st, dr);
if (i + 1 + Len[1][i] > best) {
best = i + 1 + Len[1][i];
poz = i + 1;
}
sol += 1LL * Len[1][i];
}
}
int main() {
fin >> Input;
s = " " + Input;
n = s.size() - 1;
Manacher_Odd();
Manacher_Even();
fout << sol;
}