算法题：最短回文串
算法思路
具体做法
构造新字符串：首先将原字符串和反转后的字符串拼接起来，用一个分隔符分隔开。比如，原字符串是 s = "aacecaaa"，那么新字符串new_s = "aacecaaa#aaacecaa"。计算 LPS（最长前后缀）数组：通过 KMP 算法，我们计算出这个新字符串的 LPS 数组。LPS 数组中的每一个元素表示该位置之前的子串的最大前后缀长度。 根据 LPS数组判断：LPS 数组的最后一个值就是反向字符串和原字符串能够匹配的最大前缀长度。通过这个信息，我们可以确定原字符串已经是回文的部分，剩下的部分就是需要补充的。 返回结果：需要补充的部分就是原字符串中未参与回文匹配的后缀部分。通过将这些字符添加到字符串的前面，我们就能得到最短回文串。
Java实现
public class ShortestPalindrome {
public String shortestPalindrome(String s) {
// 如果字符串为空或只有一个字符，直接返回
if (s == null || s.length() <= 1) {
return s;
}
// 反转字符串
String reversed = new StringBuilder(s).reverse().toString();
// 拼接原字符串和反转字符串，中间加个#分隔，避免重复匹配
String newString = s + "#" + reversed;
// 计算LPS数组
int[] lps = buildLPS(newString);
// LPS数组最后一个值即为原字符串和反转字符串的最大匹配长度
int longestPrefix = lps[lps.length - 1];
// 根据最长回文前缀的长度来确定需要添加的字符
String suffixToAdd = s.substring(longestPrefix);
// 将反转的后缀添加到原字符串的前面
return new StringBuilder(suffixToAdd).reverse().toString() + s;
}
// 构建LPS数组
private int[] buildLPS(String s) {
int[] lps = new int[s.length()];
int j = 0; // 前缀的末尾
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = lps[j - 1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
lps[i] = j;
}
return lps;
}
public static void main(String[] args) {
ShortestPalindrome solution = new ShortestPalindrome();
String s = "aacecaaa";
System.out.println(solution.shortestPalindrome(s)); // 输出 "aaacecaaa"
}
}
代码解析
反转字符串：我们先反转原字符串，这样我们就能比较原字符串和反向字符串。 构建新的字符串：通过将原字符串和反转字符串拼接，间隔符 #是为了确保我们不会出现字符的重复匹配。LPS数组的计算：用 KMP 算法计算出最长的回文前缀，即原字符串和反转字符串相匹配的部分。 生成最短回文串：根据 LPS 数组的最后一个值来确定最短回文串需要添加的字符。然后将这些字符反转并添加到原字符串的前面。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
