马拉车
用于O(n)找出字符串的所有回文子串
cpp
std::vector<int> manacher(std::vector<int> s) {
std::vector<int> t{0};
for (auto c : s) {
t.push_back(c);
t.push_back(0);
}
int n = t.size();
std::vector<int> r(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + r[j] > i) {
r[i] = std::min(r[2 * j - i], j + r[j] - i);
}
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
r[i] += 1;
}
if (i + r[i] > j + r[j]) {
j = i;
}
}
return r;
}