数据结构与算法之Manacher算法

素颜马尾好姑娘i 2021-12-16 13:53 290阅读 0赞

# 数据结构与算法之Manacher算法 #

--------------------

## 目录 ##

1.  Manacher算法概述
2.  Manacher算法代码实现
3.  扩展题——如果只能向字符串后面添加字符，怎么让整体串变成回文串，要求填的字符最少

--------------------

### 1. Manacher算法概述 ###

1.  Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。
2.  详细请见博客：[https://www.jianshu.com/p/116aa58b7d81][https_www.jianshu.com_p_116aa58b7d81] ，写的很好，就不再复述一遍了。

--------------------

### 2. Manacher算法代码实现 ###

public class Code_Manacher {
        
    
        public static char[] manacherString(String str) {
        
            char[] charArray = str.toCharArray();
            char[] res = new char[charArray.length * 2 + 1];
            int index = 0;
            for (int i = 0; i < res.length; i++) {
        
                res[i] = (i & 1) == 0 ? '#' : charArray[index++];
            }
            return res;
        }
    
        public static int maxLcpsLength(String str) {
        
            if (str == null || str.length() == 0) {
        
                return 0;
            }
            char[] charArr = manacherString(str);
            int[] pArr = new int[charArr.length]; //回文半径
            int C = -1;
            int R = -1;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i != charArr.length; i++) {
        
                //区分情况一和情况二
                pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
    //          情况1 ：i在R外， 暴力扩
    //			情况2 ： i在R里， i'的回文在L，R内
    //			情况3 ： i在R里，i'的回文在L，R外
    //			情况4 ：i'回文左边界和L压线，从R的右边扩。
                //如果要验的区域没越界，并且左边区域也没越界。就再扩一下，如果是情况二和情况三，那么会失败
                while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
        
                    //情况一，情况四
                    if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                        pArr[i]++;
                    else {
        
                        //情况二，情况三
                        break;
                    }
                }
                if (i + pArr[i] > R) {
        
                    R = i + pArr[i];
                    C = i;
                }
                max = Math.max(max, pArr[i]);
            }
            return max - 1;
        }
    
        public static void main(String[] args) {
        
            String str1 = "abc1234321ab";
    
            System.out.println(maxLcpsLength(str1));
    
        }
    
    }

编译结果：  
![在这里插入图片描述][20190705213456577.png]

--------------------

### 3. 扩展题——如果只能向字符串后面添加字符，怎么让整体串变成回文串，要求填的字符最少 ###

1.  代码实现

public class Code_Manacher_ShortestEnd {
        
    
    	public static char[] manacherString(String str) {
        
    		char[] charArr = str.toCharArray();
    		char[] res = new char[str.length() * 2 + 1];
    		int index = 0;
    		for (int i = 0; i != res.length; i++) {
        
    			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    		}
    		return res;
    	}
    
    	public static String shortestEnd(String str) {
        
    		if (str == null || str.length() == 0) {
        
    			return null;
    		}
    		char[] charArr = manacherString(str);
    		int[] pArr = new int[charArr.length];
    		int index = -1;
    		int pR = -1;
    		int maxContainsEnd = -1;
    		for (int i = 0; i != charArr.length; i++) {
        
    			pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
    			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
        
    				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
    					pArr[i]++;
    				else {
        
    					break;
    				}
    			}
    			if (i + pArr[i] > pR) {
        
    				pR = i + pArr[i];
    				index = i;
    			}
    			if (pR == charArr.length) {
        
    				maxContainsEnd = pArr[i];
    				break;
    			}
    		}
    		char[] res = new char[str.length() - maxContainsEnd + 1];
    		for (int i = 0; i < res.length; i++) {
        
    			res[res.length - 1 - i] = charArr[i * 2 + 1];
    		}
    		return String.valueOf(res);
    	}
    
    	public static void main(String[] args) {
        
    		String str2 = "abcd123321";
    		System.out.println(str2);
    		System.out.println(shortestEnd(str2));
    
    	}
    
    }

编译结果：  
![在这里插入图片描述][20190705213635783.png]

[https_www.jianshu.com_p_116aa58b7d81]: https://www.jianshu.com/p/116aa58b7d81
[20190705213456577.png]: /images/20211214/7d8f27c462bf47c684e7201639e64117.png
[20190705213635783.png]: /images/20211214/0c91828523dc454f8c02aa6a180673e0.png