当前位置： 面试刷题>> 最短回文串 (经典算法题500道)
### 题目描述补充
**题目：最短回文串**
给定一个字符串 `s`，要求找到在 `s` 的右侧添加最少的字符（可以是原字符串中的字符），使得新的字符串成为一个回文串。返回这个最短回文串的右侧添加部分，以及这个添加部分的长度。
**示例 1**:
```
输入: s = "abcabc"
输出: "abc"
解释: 最短回文串是 "abcabcabc"，在原字符串右侧添加了 "abc"。
```
**示例 2**:
```
输入: s = "a"
输出: ""
解释: 最短回文串就是原字符串 "a"，不需要添加任何字符。
```
### PHP 代码示例
```php
function shortestPalindrome($s) {
$reversed = strrev($s); // 反转字符串
$concat = $s . '#' . $reversed; // 拼接原字符串、分隔符和反转字符串
$n = strlen($concat);
// 使用KMP算法中的部分匹配表（next数组）来找到最长公共前后缀
$lps = array_fill(0, $n, 0);
$j = 0;
$i = 1;
while ($i < $n) {
if ($concat[$i] == $concat[$j]) {
$lps[$i] = $j + 1;
$i++;
$j++;
} elseif ($j != 0) {
$j = $lps[$j - 1];
} else {
$lps[$i] = 0;
$i++;
}
}
// lps数组中的最后一个值即是最长公共前后缀的长度
// 需要添加的字符是反转字符串中去掉最长公共前后缀的部分
return substr($reversed, 0, $n - 1 - $lps[$n - 1]);
}
// 测试
echo shortestPalindrome("abcabc"); // 输出 "abc"
echo shortestPalindrome("a"); // 输出 ""
```
### Python 代码示例
```python
def shortestPalindrome(s: str) -> str:
reversed_s = s[::-1] # 反转字符串
concat = s + '#' + reversed_s # 拼接字符串
n = len(concat)
# 使用KMP算法求部分匹配表（next数组）
lps = [0] * n
j = 0
i = 1
while i < n:
if concat[i] == concat[j]:
lps[i] = j + 1
i += 1
j += 1
elif j != 0:
j = lps[j - 1]
else:
lps[i] = 0
i += 1
# 去掉最长公共前后缀的部分
return reversed_s[:n - 1 - lps[-1]]
# 测试
print(shortestPalindrome("abcabc")) # 输出 "abc"
print(shortestPalindrome("a")) # 输出 ""
```
### JavaScript 代码示例
```javascript
function shortestPalindrome(s) {
const reversed = s.split('').reverse().join(''); // 反转字符串
const concat = s + '#' + reversed; // 拼接字符串
const n = concat.length;
// 使用KMP算法求部分匹配表（next数组）
const lps = new Array(n).fill(0);
let j = 0;
for (let i = 1; i < n; i++) {
if (concat[i] === concat[j]) {
lps[i] = j + 1;
j++;
} else if (j !== 0) {
j = lps[j - 1];
}
}
// 去掉最长公共前后缀的部分
return reversed.substring(0, n - 1 - lps[n - 1]);
}
// 测试
console.log(shortestPalindrome("abcabc")); // 输出 "abc"
console.log(shortestPalindrome("a")); // 输出 ""
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖算法、数据结构、编程语言等多个方面，帮助大家提升编程能力。