Pagini recente » Cod sursa (job #795208) | Cod sursa (job #3235074) | Cod sursa (job #999472) | Cod sursa (job #3292551) | Cod sursa (job #3288674)
#include <fstream>
#include <string>
using namespace std;
const int nmax = 1e6;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
uint64_t manacher[2 * nmax + 1], middle, ans;
string t, s;
int main() {
fin >> t;
// doar palindroame impare
for (int i = 0; i < t.size(); i++) {
s += '#';
s += t[i];
}
s += '#';
// construim manacher[]
middle = -1;
for (int i = 0; i < s.size(); i++) {
// daca putem lua din spate
if (middle != -1 && middle + manacher[middle] - 1 >= i) {
manacher[i] =
min(manacher[middle - (i - middle)], middle + manacher[middle] - i);
}
// brut
while (i + manacher[i] < s.size() && i - manacher[i] >= 0 &&
s[i + manacher[i]] == s[i - manacher[i]]) {
manacher[i]++;
}
// actualizam
if (middle == -1 || i + manacher[i] > middle + manacher[middle]) {
middle = i;
}
}
for (int i = 0; i < s.size(); i++) {
ans += manacher[i] / 2;
}
fout << ans << '\n';
return 0;
}
/*
Numarati subsecventele palindrom pe care sirul de caractere le contine.
https://www.infoarena.ro/problema/pscpld
*/