【Leetcode】5.最长回文子串C++（马拉车算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Leetcode】5.最长回文子串C++（马拉车算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1189字，纯文字阅读大概需要2分钟。
内容图文
/*
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
*/
#include "iostream"
#include "string"
#include "vector"
#define MAX 1000
using namespace std;
class Solution
{
public:
string longestPalindrome(string s)
{
string man_s;
int i, s_size = s.size();
if (s_size <= 1)
return s;
// 预处理
man_s.push_back('$');
for (i = 0; i < s_size; i++)
{
man_s.push_back('#');
man_s.push_back(s[i]);
}
man_s.push_back('#');
man_s.push_back('@');
// 辅助数组p
int len = man_s.size();
vector<int> p(len, 0);
// 寻找最长回文字符串
int id = 0; //回文子串的中心位置
int mx = 0; // 回文子串的最后位置
int j; // j=2*id-i是i关于id的对称点
// 关键公式：p[i]=min(mx-i, p[2*id-i])
for (i = 1; i < len - 1; i++)
{
if (i < mx)
{
j = 2 * id - i;
p[i] = mx < p[j] ? mx : p[j];
}
// 向两边扩展,$和@防止越界
while (man_s[i - p[i] - 1] == man_s[i + p[i] + 1])
{
p[i] += 1;
}
// 更新中心
if (p[i] > mx)
{
mx = p[i];
id = i;
}
}
string ans;
for (i = id - mx; i <= id + mx; i++)
{
if (man_s[i] != '#')
{
ans.push_back(man_s[i]);
}
}
return ans;
}
};
int main(void)
{
string s;
cin >> s;
Solution So;
string ans = So.longestPalindrome(s);
cout << ans << endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的【Leetcode】5.最长回文子串C++（马拉车算法）全部内容，希望文章能够帮你解决【Leetcode】5.最长回文子串C++（马拉车算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】