题目
随意给定一个字符串,求必须在该字符串后面依次添加哪些字符,使得整体是回文字符串。
题目实质
必须包含源字符串最后一个字符的情况下,最长回文子串是多长。然后把前面不是回文的字符串逆序加到后面就行了。
注意:不是求回文串的整体最长,是必须包含最后一个字符的情况下的最长!!!
在Manacher算法的基础上稍微做一点改进即可,**从0位置开始扩的时候,一旦找到以某个X位置为中心点的有边界正好罩住所有字符的时候,就停!X就是最早扩住
最后一个字符的中心**。也就是找到了最长且包含最后一个字符的中心,因为是从左往右开始扩的。
小的改进
如果要求返回最长回文串是啥,可以通过下标换算得到最长回文串的最后一个字符的位置。
也就是说,
最长回文串的结尾位置可以通过(处理串中的结尾位置-1)/ 2 得到原始串的结尾。奇数偶数时候都一样。
代码
package com.harrison.class17;
/**
* @author Harrison
* @create 2022-03-30-13:14
* @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
*/
public class Code02_AddShortestEnd {
public static char[] manacherString(String s) {
char[] str = s.toCharArray();
char[] res = new char[2 * str.length + 1];
int index = 0;
for (int i = 0; i != res.length; i++) {
res[i] = (i & 1) == 0 ? '#' : str[index++];
}
return res;
}
public static String shortestString(String s) {
if (s == null || s.length() == 0) {
return null;
}
char[] str = manacherString(s);
int[] pArr = new int[str.length];
int C = -1;
int R = -1;
int maxContainsEnd = -1;
for (int i = 0; i < str.length; i++) {
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
if (str[i + pArr[i]] == str[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = R;
}
if (R == str.length) {
maxContainsEnd = pArr[i];
break;
}
}
char[] res = new char[s.length() - maxContainsEnd + 1];
for (int i = 0; i < res.length; i++) {
res[res.length - 1 - i] = str[2 * i + 1];
}
return String.valueOf(res);
}
public static void main(String[] args) {
String str1 = "abcd123321";
System.out.println(shortestString(str1));
}
}