Pagini recente » Cod sursa (job #1560162) | Cod sursa (job #2379357) | Cod sursa (job #3129995) | Cod sursa (job #2744483) | Cod sursa (job #2317057)
#include <fstream>
using namespace std;
int main() {
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string s;
in >> s;
int m = s.size();
int v[2 * m];
char a[2 * m];
for (int i = 0; i < m; i++) {
a[2 * i] = '*';
a[2 * i + 1] = s[i];
}
a[2 * m] = '*';
a[2 * m + 1] = '\0';
m = 2 * m + 1;
//Manacher
int j, centru = 0, dr = 0, sol = 0;
for (int i = 0; i < m; i++) {
if (dr <= i) {
v[i] = 1;
j = 1;
while (i - j >= 0 && i + j < m && a[i - j] == a[i + j]) {
j++;
v[i]++;
}
dr = i + j - 1;
centru = i;
} else {
v[i] = min(dr - i + 1, v[2 * centru - i]);
if (v[i] + i - 1 >= dr) {
j = v[i];
while (i - j >= 0 && i + j < m && a[i - j] == a[i + j]) {
j++;
v[i]++;
}
dr = i + j - 1;
centru = i;
}
}
sol += v[i] / 2;
}
out << sol;
return 0;
}