最长回文子串问题 题目链接:https://www.patest.cn/contests/gplt/L2-008
枚举子串
超时一个点 复杂度O(n^3)
code
1 |
|
枚举中轴
这个方法就是枚举轴,然后从轴向两边扩展。 复杂度O(n^2)
需要注意的是,轴有两种情况: 1. 以中间一个数字为轴 2. 以中间两个数字为轴
code
1 |
|
Manacher
复杂度:O(n)
这个算法看了两天才看明白。 具体这个算法可以看我的下一篇博客:
code
1 |
|
最长回文子串问题 题目链接:https://www.patest.cn/contests/gplt/L2-008
超时一个点 复杂度O(n^3)
1 | #include<bits/stdc++.h> |
这个方法就是枚举轴,然后从轴向两边扩展。 复杂度O(n^2)
需要注意的是,轴有两种情况: 1. 以中间一个数字为轴 2. 以中间两个数字为轴
1 | #include<bits/stdc++.h> |
复杂度:O(n)
这个算法看了两天才看明白。 具体这个算法可以看我的下一篇博客:
1 | #include<bits/stdc++.h> |
文章作者:Xie Keyi
发布时间:2018年03月26日 - 19:03
原始链接:https://xiekeyi98.com/fb32b34c.html
许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。