5。最长的全回文底带。 Thoery问题。 ComputersCi/Leetcode
我正在对Leetcode上做最长的alindromic substring问题，许多视频建议使用从中心扩展来解决此问题。但是，我真的不理解他们的理论。请帮助我理解他们的理论，谢谢。
如果我的字符串是“ abadefg”或“ gfedaba”，那么做奇数/什至从中心开始是没有意义的呢？
谢谢。
I am doing the Longest Palindromic Substring question on leetcode, and a lot of video suggest using the expanding from center to solve this problem. However, I dont really understand their theory. please help me understand their theory, thanks.
what if my string is "abadefg" or "gfedaba" then it wouldnt make sense to do odd/even starting from center?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为您正在误解该算法。
Manacher算法的最简单形式采用了
abadefg之类的字符串，并将其转换为a*b*a*d*e*e*f*f*g。然后，它从左到右工作，并提出一个问题：“最长的具有该角色作为中心的回文是什么”。完成后，您会弄清楚总体上发现的最长的回旋室，然后删除星号。算法的替代形式不需要添加星号。取而代之的是，它曾经在弦上进行两次通过，一次找到均匀的alentlindromes，一次找到奇怪的回文。但是两个都不是“从中心开始”。
搜索网络和YouTube查看Manacher的算法将为您找到许多好的文章和解释。
I think you are misunderstanding the algorithm.
The simplest form of Manacher's algorithm takes a string like
abadefgand converts it intoa*b*a*d*e*f*g. It then works left-to-right and asks the question "What is the longest palindrome that has this character as the center". When you're done, you figure out what the longest palindrome you found overall, and remove the asterisks.There is an alternate form of the algorithm that doesn't need to add the asterisks. Instead it makes two passes over the string, once to find even-length palindromes and once to find odd-length palindromes. But neither "starts at the center".
Searching the Web and Youtube for Manacher's algorithm will find you many good articles and explanations.