刷题DAY13

谁践踏了优雅 2023-10-14 10:47 79阅读 0赞

## 题目一 ##

手撕mannacher算法

总之是找最长回文字符串

最暴力的解法是什么呢

你就枚举每一个字符 往左右扩 看它每步一不一样 但是这个恶心在哪呢 1221这样的回文字符串 你找不到它的对称轴 它是虚轴

那我们怎么优化呢 1\#2\#2\#1 哎 这样就能把虚轴给枚举出来了

哎 你可能会问 啊 那我字符串中本来就有\#咋办 假如说 \#22\# 我转化成\#\#2\#2\#\# 影响吗? 他该是回文还是回文啊 不是回文咋填都不是回文 填一都行

但是这样实在是太暴力了 我们选择进行优化 也就引出了mannacher算法

先了解几个基本概念

回文半径&回文直径

11211

回文半径 就是从一端开始数 这个回文数组 数一半包括中心点 也就是3

回文直径 就是全部的 5

回文最右边界 那就是4(第五个位置)

中心 就是2(第三个位置)

我们设i 为当前位置

c为最长回文半径的中心

pArr\[i\] 是i位置的最长回文半径

R是最长回文边界

当i>R时

没有优化的可能 往外扩吧

当i<R时

设它以C为中心的对称点为i\*

(1) i\*的回文区域在 C的回文区域之内

那么i\*的回文半径 就是i的回文半径

(2) i\*的回文区域超过了 C的回文区域

那么i的回文半径就是 R-i(i到C的最右边界的一段)

(3)i\*的回文区域正好和C的回文区域重合

我们只知道 i到C的最右边界的这一段 肯定是回文的 但下一个 只能慢慢推

public static int manacher(String string) {
        	if (string == null || string.length() == 0) {
    			return 0;
    		}
    		char[] chars = tochars(string); 
    		int R = -1;
    		int max = 0;
    		int C = -1;
    		int [] parr = new int [chars.length];
    		for (int i = 0; i < chars.length; i++) {
    			parr[i] = R>i?Math.min(R-i,parr[2*C-1]):1;
    			while(i+parr[i]<chars.length&& i - parr[i] > -1){//有一边越界了都不行
    				if(chars[i+parr[i]]==chars[i-parr[i]]) {
    					parr[i]++;
    				}else {
    					break;
    				}
    			}
    			max = Math.max(max, parr[i]);
    			if(i+parr[i]>R) {
    				C = i;
    				R = i+parr[i];
    			}
    		}
    	   return max-1;
    	}
        public static char [] tochars(String string) {
    		char [] str = string.toCharArray();
    		char [] res = new char [str.length*2+1];
    		int index = 0;
    		for(int i = 0;i<res.length;i++) {
    			if(i%2==0) {
    				res[i] = '#';
    			}else {
    				res[i] = str[index++];
    			}
    		}
    		return res;
    	}

pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;

解释下这行代码

pArr\[2\*C - i\]是i的对称位置的回文半径

R-i是右边界到i的距离

分别讨论三种情况 当i在R内 且i\*的回文区域全在 C的回文区域内 i的回文区域取pArr\[2\*C - i\]

当i在R内 且i\*的回文区域超出的C的回文区域 取R-i

当正好边界位置 都一样

然后这个值就是可以优化得出的"回文半径至少多长" 然后后面的再自己扩去

## 题目二 ##

添加最短字符串 让整体字符串成 回文字符串 返回这个最短字符串

是添加字符串 而不是插入字符

我们要找到必须包含最后一个字符的回文字符串有多长 那就是最先包含最后一个字符的回文字符串有多长

然后就能求出 非回文的字符串有多长 我们需要补充的长度就求出来了

public static String manacher(String string) {
        	if (string == null || string.length() == 0) {
    			return 0;
    		}
    		char[] chars = tochars(string); 
    		int R = -1;
    		int cur = 0;
    		int C = -1;
    		int [] parr = new int [chars.length];
    		for (int i = 0; i < chars.length; i++) {
    			parr[i] = R>i?Math.min(R-i,parr[2*C-1]):1;
    			while(i+parr[i]<chars.length&& i - parr[i] > -1){//有一边越界了都不行
    				if(chars[i+parr[i]]==chars[i-parr[i]]) {
    					parr[i]++;
    					
    				}else {
    					break;
    				}
    			}
    			if(i+parr[i]>R) {
    				C = i;
    				R = i+parr[i];
    			}
    			if (R == string.length()) {
    				cur = parr[i];
    				break;
    			}
    		}
    		char[] res = new char[string.length() - cur + 1];
    		for (int i = 0; i < res.length; i++) {
    			res[res.length - 1 - i] = chars[i * 2 + 1];
    		}
    		return String.valueOf(res);
    
    	}