输入一个字符串输出最短原串

题目描述

一个字符串经过对称扩展之后就是一个回文串，如果继续对称扩展下去就会形成一个很长的字符串，例如:“AC”对称扩展一次变成“ACCA”，再进行对称扩展一次就变成了“ACCAACCA”，现在给你一个字符串，请你判断这个字符串可能的最短原串是什么?

输入格式

多实例，每个实例输入一行字符串，长度不大于1000。

输出格式

对应每个实例输出一行字符串，为输入字符串的最短原串。

输入样例

在这里给出一组输入。例如:ACMMCA

输出样例

在这里给出相应的输出。例如:ACM

实现代码

这道题可以使用 Manacher 算法来解决。Manacher 算法是一种用于求解最长回文子串的算法，同时也能够扩展到求解最短原串。

Manacher 算法的基本思路是：对于每个位置 i，求出以该位置为中心的最长回文半径 p[i]，然后在所有的 p[i] 中，找到最大值 maxLen，该 maxLen 对应的中心位置 i 就是最长回文子串的中心。具体实现时，可以利用回文串的对称性，避免重复计算。

对于这道题目，我们需要先对输入的字符串进行对称扩展，得到一个新的字符串 s，然后再运用 Manacher 算法求出最长回文子串的长度，最后取回文子串的中心点，就能够得到最短原串了。

以下是 C 语言的代码实现：

#include <stdio.h>
#include <string.h>

#define MAXN 2010

char str[MAXN];   // 输入的字符串
char s[MAXN * 2]; // 对称扩展后的字符串
int p[MAXN * 2];  // 记录以每个位置为中心的最长回文半径

int main() {
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        // 对称扩展字符串
        for (int i = 0; i < len; i++) {
            s[i * 2] = '#';
            s[i * 2 + 1] = str[i];
        }
        s[len * 2] = '#'; // 特殊处理最后一个字符
        int n = len * 2 + 1; // 对称扩展后的字符串长度
        // 计算以每个位置为中心的最长回文半径
        int mx = 0, id = 0;
        for (int i = 0; i < n; i++) {
            if (i < mx) {
                p[i] = p[2 * id - i];
                if (p[i] > mx - i) p[i] = mx - i;
            } else {
                p[i] = 1;
            }
            while (i - p[i] >= 0 && i + p[i] < n && s[i - p[i]] == s[i + p[i]]) {
                p[i]++;
            }
            if (i + p[i] > mx) {
                mx = i + p[i];
                id = i;
            }
        }
        // 找到最长回文子串的中心点
        int maxLen = 0, pos = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                pos = i;
            }
        }
        // 取回文子串的中心点，得到最短原串
        int start = (pos - maxLen + 1) / 2;
        int end = start + maxLen - 1;
        str[end] = '\0'; // 字符串末尾加上结束符
        printf("%s\n", str + start);
    }
    return 0;
}

其中，对称扩展字符串的部分使用了一个 for 循环，每次将一个字符后面插入一个字符 ‘#’，这样做是为了处理在字符串长度为奇数时，最长回文子串的中心点可能在一个字符上的情况。

Manacher 算法的部分和求解最长回文子串是类似的。计算完成以后，我们需要找到最长回文子串的中心点，然后取该中心点左侧的所有字符，就是最短原串。

运行结果