前言：
目前咱们对“manacher算法时间复杂度”大致比较着重，朋友们都想要剖析一些“manacher算法时间复杂度”的相关文章。那么小编也在网上搜集了一些关于“manacher算法时间复杂度””的相关文章，希望各位老铁们能喜欢，兄弟们快快来学习一下吧！【方法1】动态规划【时间复杂度 O(n^2) 空间复杂度 O(n^2)】
发现规律：某事物符合某一条件且该事物的子集也符合这一条件时，可以考虑dp，即动态规划
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
状态转移方程：只有 s[i+1:j-1] 是回文串，并且第 i 和 j 个字母相同时，s[i:j] 才会是回文串。
代码思路：外循环当前寻找回文串的长度，表示为 l +1。l 初始化为0是因为可能就没有回文串
这个方法还是很好理解的
class Solution { public String longestPalindrome(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; String ans = ""; for (int l = 0; l < n; ++l) { for (int i = 0; i + l < n; ++i) { int j = i + l; if (l == 0) { dp[i][j] = true; } else if (l == 1) { dp[i][j] = (s.charAt(i) == s.charAt(j)); } else { dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]); } if (dp[i][j] && l + 1 > ans.length()) { ans = s.substring(i, i + l + 1); } } } return ans; }}【方法2】中心扩展【时间复杂度 O(n^2) 空间复杂度 O(n^2)】
与动态规划相反，这个方法是从里到外判断两侧字母是否相等
循环主串的每一个位置，以当前位置为中心进行扩展（注意回文串长度会有单双的情况），然后选取最长回文串
【方法3】Manacher 算法【时间复杂度 O(n) 空间复杂度 O(n)】
十分复杂，直接告辞
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
