哈希倒闭了怎么办/jk
2026-07-14 21:36:22
发布于：广东
38阅读
0回复
0点赞
书接上回。
发现中考英语作文没拿满分，严肃意识到自己不会字符串。
由于现在是上午，所以只学一个算法，剩下一个放在下午。 都快打 CF 了我还没学我怎么这么区。
Manacher
将每个字符两边用一个滚木包裹，使得所有回文串长度都为奇数。
考虑维护此时每个 为中心的最长回文子串端点与 的距离 。则原串答案显然为 。
考虑维护目前小于 为中心的最长回文子串中右端点最大值 及其中心 。
由回文串定义（关于中心对称）得， 为中心， 为右端点的串一定回文。
然后暴力扩展，更新 与 。每次暴力扩展一定会使 移动 ，而 一共只会移动 次，所以时间复杂度为 。
namespace cjdst{
void solve(){
std::string a;
std::cin >> a;
int n = a.size() * 2 + 1;
std::string b = " ";
for(char c:a){
b += c;
b += ' ';
}
std::swap(a, b);
std::vector <int> p(n + 5);
int mid = -1, r = 0;
for(int i = 1; i <= n; i++){
if(i > r){
mid = r = i;
}
p[i] = std::min(r - i, p[mid * 2 - i]);
while(i - p[i] > 1 && i + p[i] < n && a[i - p[i] - 1] == a[i + p[i] + 1]){
p[i]++;
}
if(i + p[i] > r){
mid = i, r = i + p[i];
}
}
std::cout << *std::max_element(p.begin() + 1, p.begin() + n + 1) << '\n';
}
}
时间复杂度：。
有帮助，赞一个