solution.md

# 最短回文串

<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

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string shortestPalindrome(string s)
    {

        string rev(s);
        reverse(rev.begin(), rev.end());
        ;
        string combine = s + "#" + rev;

        vector<int> lps(combine.length(), 0);
        int remove = getLPS(combine, lps);

        string prepend = rev.substr(0, rev.length() - remove);
        return prepend + s;
    }

    int getLPS(string s, vector<int> &lps)
    {

        int j = 0, i = 1;

        while (i < s.length())
        {

            if (s[i] == s[j])
            {
                lps[i] = j + 1;
                i++;
                j++;
            }
            else
            {

                if (j != 0)
                {
                    j = lps[j - 1];
                }
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps[lps.size() - 1];
    }
};


```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```