Pagini recente » Cod sursa (job #2333157) | Cod sursa (job #2677998) | Cod sursa (job #2625572) | Cod sursa (job #978822) | Cod sursa (job #2692008)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int n, center, max_extended, nrpali[2000100];
string s = " *";
void brute_force_extend(int mid) {
int st = mid - nrpali[mid] + 1;
int dr = mid + nrpali[mid] - 1;
while (st > 1 && dr < n) {
if (s[st - 1] != s[dr + 1])
break;
st--;
dr++;
nrpali[mid]++;
}
if (dr > max_extended) {
max_extended = dr;
center = mid;
}
}
int main() {
fin.tie(0);fout.tie(0);
ios::sync_with_stdio(0);
string s_ini;
fin >> s_ini;
n = 2 * s_ini.length() + 1;
for (int i = 0; i < (int)s_ini.length(); i++) {
s += s_ini[i];
s += "*";
}
for (int i = 1; i <= n; i++)
nrpali[i] = 1;
for (int i = 1; i <= n; i++) {
if (i > max_extended)
brute_force_extend(i);
else {
int opus = center - (i - center);
if (i + nrpali[opus] < max_extended)
nrpali[i] = nrpali[opus];
else
brute_force_extend(i);
}
}
ll total = 0;
for (int i = 1; i <= n; i++)
total += nrpali[i] / 2;
fout << total;
return 0;
}