214. Shortest Palindrome

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

```Input: s = "aacecaaa"
Output: "aaacecaaa"
```

Example 2:

```Input: s = "abcd"
Output: "dcbabcd"
```

Constraints:

• `0 <= s.length <= 5 * 104`
• `s` consists of lowercase English letters only.

214. Shortest Palindrome
``````struct Solution;
use std::iter::once;

impl Solution {
fn shortest_palindrome(s: String) -> String {
let n = s.len();
let s_new: Vec<char> = s.chars().chain(once('#')).chain(s.chars().rev()).collect();
let n_new = s_new.len();
let mut f = vec![0; n_new];
for i in 1..n_new {
let mut t = f[i - 1];
while t > 0 && s_new[i] != s_new[t] {
t = f[t - 1];
}
if s_new[i] == s_new[t] {
t += 1;
}
f[i] = t;
}
s.chars()
.rev()
.take(n - f.last().unwrap())
.chain(s.chars())
.collect()
}
}

#[test]
fn test() {
let s = "aacecaaa".to_string();
let res = "aaacecaaa".to_string();
assert_eq!(Solution::shortest_palindrome(s), res);
let s = "abcd".to_string();
let res = "dcbabcd".to_string();
assert_eq!(Solution::shortest_palindrome(s), res);
}
``````