企业官网建设流程全解析

Approach: KMP — find the longest palindromic prefix

The shortest palindrome is formed by taking the longest palindromic prefix of
“s”, then prepending the reverse of the leftover suffix.

To find that prefix in
“O(n)”, build
“t = s + “#” + reverse(s)” and compute KMP’s LPS array. The final LPS value is exactly the length of the longest palindromic prefix — because it’s the longest prefix of
“s” that also matches a suffix of
“reverse(s)”, which is the definition of a palindrome.

class Solution {
public String shortestPalindrome(String s) {
String rev = new StringBuilder(s).reverse().toString();
String t = s + “#” + rev; // ‘#’ never appears in s

int[] lps = buildLPS(t); int palPrefixLen = lps[t.length() - 1]; return rev.substring(0, s.length() - palPrefixLen) + s; } /** lps[i] = length of the longest proper prefix of t[0..i] that is also a suffix */ private int[] buildLPS(String t) { int[] lps = new int[t.length()]; for (int i = 1, len = 0; i < t.length(); ) { if (t.charAt(i) == t.charAt(len)) { lps[i++] = ++len; } else if (len > 0) { len = lps[len - 1]; // fall back, don't advance i } else { lps[i++] = 0; } } return lps; }

}

Walkthrough (
“s = “aacecaaa””)

“rev = “aaacecaa””,
“t = “aacecaaa#aaacecaa””

“lps” ends at
“7” → palindromic prefix
““aacecaa””

• Leftover
  ““a”” reversed is
  ““a”” →
  ““a” + “aacecaaa”” =
  ““aaacecaaa””

Complexity

• Time
  “O(n)” — LPS is built in a single pass
• Space
  “O(n)” — the LPS array plus the combined string

Notes

• The
  “‘#’” separator is essential: without it, the prefix and suffix could overlap into the boundary and over-count.
• The
  “len > 0” branch must not increment
  “i” — that’s the standard KMP fallback and the most common source of an infinite loop if you get it wrong.
• An alternative is Manacher’s algorithm with a check that the palindrome touches index
  “0”, but KMP is shorter and easier to get right in an interview.