回文串实现--轻松理解Manacher算法
2021/7/10 20:10:09
本文主要是介绍回文串实现--轻松理解Manacher算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
首先说一下什么是回文串?
回文串就是一个字符串的逆序和正序相同,此字符串就是回文串。比如:abcdedc中的 cdedc就是会问串。那么回文串问题怎么解决呢?
前置操作:
因为回文串分为奇数串和偶数串,比如奇数串为:abcba这样是以c为中心向两边扩,直接遍历字符串就行了,但是如果遇到偶数串的时候直接遍历,判断两边字符是否相等就不行了,比如abba这样的字符,以两个b之间的位置作为中心,这样就需要添加辅助的字符,所以我们拿到字符串时,需要对字符串进行处理,把字符串的每个位置都插入其他字符,比如#a#b#b#a#这样我们直接遍历就行了,插入的辅助字符是否可以和已有字符相同呢?答案是:可以的,因为就算插入了辅助字符,还是已有字符和已有字符相比较,辅助字符和辅助字符相比较,所以是可以的。
方法一:朴素法
我们可以遍历每个字符串,然后向前向后分别扩充,最后得到最长的回文串。
时间复杂度为:O(n^2),空间复杂度为:O(1)代码实现如下:
public String longestPalindrome(String s) { StringBuilder sb = new StringBuilder("#"); for (int i = 0; i < s.length(); i++) { sb.append(s.charAt(i)).append("#"); } char[] chars = sb.toString().toCharArray(); String maxStr = ""; int max = 0; for (int i = 0; i < chars.length; i++) { int j = 1; while (i + j < chars.length && i - j >= 0 && chars[i - j] == chars[i + j]) { j++; } if (max < j) { max = j; maxStr = sb.substring(i - j + 1,i + j); } } return maxStr.replaceAll("#",""); }
方法二:Manacher算法
此方法的好处是时间复杂度可以接近O(n),通过维护一个半径数组,可以实现加速匹配字符串。有一个R为最右边界,维护匹配字符的最右边的字符。还有一个中心位置C位,这个的作用为可以快速找到回文串L-C-R之间的所有位置的半径。
主要分为四种情况:
- 右边界小于遍历的字符下标,则需要暴力匹配下一个字符,然后更新R。
- 匹配的字符小于右边界,并且C左边对应的半径也小于最左边界,则直接使用左边的半径。比如abcbdedbcbaerft,e中C位R为a,遍历到第二个c位置时就可以直接拿到第一个c的半径,因为其半径在最左边界内部。
- 匹配的字符小于右边界,但是C左边对应的半径大于左边界,则可以直接把半径写成R-i,因为如果R+1的字符等于L-1的字符的话,则还可以扩,之所以没有扩,就说明不等于。
- 匹配的字符小于右边界,但C左边对应的半径等于右边界,这种情况则需要暴力扩展了。可以直接扩展R+1位置。
代码实现如下:
public String longestPalindrome(String s) { StringBuilder sb = new StringBuilder("#"); for (int i = 0; i < s.length(); i++) { sb.append(s.charAt(i)).append("#"); } char[] chars = sb.toString().toCharArray(); int[] ids = new int[chars.length]; // 回文半径数组 int C = -1; // 中心 int R = -1; // 最右边界,最右边有效区域为R-1 String maxStr = ""; int max = 0; for (int i = 0; i < chars.length; i++) { // ids数组加速i的匹配速度,如果之前匹配过了,则越过直接匹配没有匹配过的。 ids[i] = R > i ? Math.min(ids[2 * C - i],R - i) : 1; // 暴力匹配按字符匹配。 while (ids[i] + i < chars.length && i - ids[i] > -1) { if (chars[ids[i] + i] == chars[i - ids[i]]) { ids[i]++; } else { break; } } // 如果遍历字符超过最右边界,则更新最右边界,及中心位置 if (R < i) { R = i + ids[i]; C = i; } if (max < ids[i]) { max = ids[i]; maxStr = sb.substring(i - ids[i] + 1,i + ids[i]); } } return maxStr.replaceAll("#",""); }
通过这个半径数组可以解决很多字符串的相似问题,半径数组是Manacher算法的核心。
这篇关于回文串实现--轻松理解Manacher算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享