# 最短回文串

<p>给定一个字符串 <em><strong>s</strong></em>，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>s = "aacecaaa"
<strong>输出：</strong>"aaacecaaa"
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>s = "abcd"
<strong>输出：</strong>"dcbabcd"
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>0 <= s.length <= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> 仅由小写英文字母组成</li>
</ul>


## template

```java
class Solution {
	public static String shortestPalindrome(String s) {
		StringBuilder r = new StringBuilder(s).reverse();
		String str = s + "#" + r;
		int[] next = next(str);

		String prefix = r.substring(0, r.length() - next[str.length()]);
		return prefix + s;
	}

	private static int[] next(String P) {
		int[] next = new int[P.length() + 1];
		next[0] = -1;
		int k = -1;
		int i = 1;

		while (i < next.length) {
			if (k == -1 || P.charAt(k) == P.charAt(i - 1)) {
				next[i++] = ++k;
			} else {
				k = next[k];
			}
		}
		return next;
	}
}

```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```