#### Shortest Palindrome

P
```/*
The function shortest_palindrome expands the given string to shortest palindrome by adding a shortest prefix.
KMP. Source：https://www.scaler.com/topics/data-structures/kmp-algorithm/
Prefix Functions and KPM. Source：https://oi-wiki.org/string/kmp/
*/

pub fn shortest_palindrome(s: &str) -> String {
if s.is_empty() {
return "".to_string();
}

let p_chars: Vec<char> = s.chars().collect();
let suffix = raw_suffix_function(&p_chars);

let mut s_chars: Vec<char> = s.chars().rev().collect();
// The prefix of the original string matches the suffix of the flipped string.
let dp = invert_suffix_function(&p_chars, &s_chars, &suffix);

s_chars.append(&mut p_chars[dp[p_chars.len() - 1]..p_chars.len()].to_vec());
s_chars.iter().collect()
}

pub fn raw_suffix_function(p_chars: &[char]) -> Vec<usize> {
let mut suffix = vec![0; p_chars.len()];
for i in 1..p_chars.len() {
let mut j = suffix[i - 1];
while j > 0 && p_chars[j] != p_chars[i] {
j = suffix[j - 1];
}
suffix[i] = j + if p_chars[j] == p_chars[i] { 1 } else { 0 };
}
suffix
}

pub fn invert_suffix_function(p_chars: &[char], s_chars: &[char], suffix: &[usize]) -> Vec<usize> {
let mut dp = vec![0; p_chars.len()];
dp[0] = if p_chars[0] == s_chars[0] { 1 } else { 0 };
for i in 1..p_chars.len() {
let mut j = dp[i - 1];
while j > 0 && s_chars[i] != p_chars[j] {
j = suffix[j - 1];
}
dp[i] = j + if s_chars[i] == p_chars[j] { 1 } else { 0 };
}
dp
}

#[cfg(test)]
mod tests {
use crate::string::shortest_palindrome;
macro_rules! test_shortest_palindrome {
(\$(\$name:ident: \$inputs:expr,)*) => {
\$(
#[test]
fn \$name() {
use crate::string::is_palindrome;
let (s, expected) = \$inputs;
assert!(is_palindrome(expected));
assert_eq!(shortest_palindrome(s), expected);
assert_eq!(shortest_palindrome(expected), expected);
}
)*
}
}
test_shortest_palindrome! {
empty: ("", ""),
extend_left_1: ("aacecaaa", "aaacecaaa"),
extend_left_2: ("abcd", "dcbabcd"),
unicode_1: ("അ", "അ"),
unicode_2: ("a牛", "牛a牛"),
}
}
```