马拉车算法 |
您所在的位置：网站首页 › 拉马车算法 › 马拉车算法 |
马拉车算法
|
马拉车算法主要是用来解决最长回文串问题的算法。 核心是利用回文串的特性进行的搜索优化 理解马拉车算法先要知道回文串的特性：回文串左右对称，例：abba，aba等等都是回文串 了解了回文串的特性下面我们去一步步推导出马拉车算法： # 由上述示例可看出当回文串长度为奇数时对称中心在字符串中的某个字符上，当回文串为偶数时对称中心在字符串两个相邻字符之间。 一、最基本的算法： 遍历所有可能的对称中心并找到以其为对称中心的最长回文串，找到所有遍历中最长的回文串。 该算法的时间复杂度为O(n^2) 二、优化 当我们遍历时需要考虑奇数和偶数的情况，为了方便，网上很多会在相邻两个字符间加入个无意义字符串（很多都是使用#），这样遍历到#的时候其实就是相当于遍历到对称中心在字符串两个相邻字符之间的这种情况，当然也可以不做此处理。 上述算法有很多重复的搜索，我们能否利用回文串的特性对其进行优化，去掉不必要的搜索？ 答案是：可以 我们再回头去看回文串的特性：左右对称 由此作为根本进行延申推理，当我们遍历的对称中心a，在某个回文串B中（B的对称中心为b）时，其相对于b的对称点为点c。有以下的结论。 1、当以c作为对称中心的最长回文串在B以内，则必定有以a为中心相同的一个回文串 这种情况下有两种情况 （1）以c作为对称中心的最长回文串没有到达B回文串的边界 这种情况以a为中心的最长回文串和以c为中心的最长回文串相同，如图所示：
（2）以c作为对称中心的最长回文串到达B回文串的边界 这种情况下，以a为中心的最长回文串可能要比以c作为对称中心的最长回文串要长，所以需要接着找其最长回文串，如图所示： 2、当以c作为对称中心的最长回文串在B以外时，则当找寻以a为对称中心的回文串时，在在B内的部分则不需要再进行回文串验证，如图所示：
三、优化后的算法 class Solution { public String longestPalindrome(String s) { int newN = s.length() * 2 + 1; char[] cs = new char[newN]; int[] len = new int[newN]; for(int i = 0; i < s.length(); i++){ cs[i * 2] = '#'; cs[i * 2 + 1] = s.charAt(i); } cs[newN - 1] = '#'; int pc = 0, mx = 0, mxCenterPos = 0; len[0] = 0; for (int i = 1; i < cs.length; i++) { int rightBorderPos = pc + mx; if(i > rightBorderPos){ int pt = 1, leftPos = i - pt, rightPos = i + pt; while(rightPos < cs.length && leftPos >= 0){ if(cs[rightPos] != cs[leftPos]){ break; } pt++; leftPos--; rightPos++; } pc = i; mx = pt - 1; len[i] = mx; if(mx > len[mxCenterPos]){ mxCenterPos = i; } } else { int symmetricPoint = pc - (i - pc); if(len[symmetricPoint] >= pc + mx - i){ int pt = pc + mx - i + 1, leftPos = i - pt, rightPos = i + pt; while(rightPos < cs.length && leftPos >= 0){ if(cs[rightPos] != cs[leftPos]){ break; } pt++; leftPos--; rightPos++; } pc = i; mx = pt - 1; len[i] = mx; if(mx > len[mxCenterPos]){ mxCenterPos = i; } }else{ len[i] = len[symmetricPoint]; } } } int stIdx = (mxCenterPos - len[mxCenterPos]) / 2; int edIdx = (mxCenterPos + len[mxCenterPos]) / 2; return s.substring(stIdx, edIdx); } }
|
【本文地址】