UVA 11475 - Extend to Palindrome

发表于 分类于 本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

Your task is, given an integer N, to make a palidrome (word that reads the same when you reverse it) of length at least N. Any palindrome will do. Easy, isn’t it? That’s what you thought before you passed it on to your inexperienced team-mate. When the contest is almost over, you find out that, that problem still isn’t solved. The problem with the code is that the strings generated are often not palindromic. There’s not enough time to start again from scratch or to debug his messy code. Seeing that the situation is desperate, you decide to simply write some additional code that takes the output and adds just enough extra characters to it to make it a palindrome and hope for the best. Your solution should take as its input a string and produce the smallest palindrome that can be formed by adding zero or more characters at its end.

输入描述

Input will consist of several lines ending in EOF. Each line will contain a non-empty string made up of
upper case and lower case English letters (‘$A$’-‘$Z$’ and ‘$a$’-‘$z$’). The length of the string will be less than
or equal to $100,000$.

输出描述

For each line of input, output will consist of exactly one line. It should contain the palindrome formed
by adding the fewest number of extra letters to the end of the corresponding input string.

样例输入

1
2
3
4
aaaa
abba
amanaplanacanal
xyz

样例输出

1
2
3
4
aaaa
abba
amanaplanacanalpanama
xyzyx

思路

题意是输入一个字符串，把它补成一个回文串输出，要求补上的字母最少。

Manacher 算法可以在$O(n)$的复杂度内计算出$d_1[i]$和$d_2[i]$，二者分别表示以位置$i$为中心的长度为奇数和长度为偶数的回文串个数。

得到$d_1[]$和$d_2[]$后，只需经过简单处理，就能补全回文串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;

string s;
int main(){
    while(cin>>s){
        /* Manacher */
        int n=s.length();
        vector<int> d1(n);
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 1 : min(d1[l + r - i], r - i);
            while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
                k++;
            }
            d1[i] = k--;
            if (i + k > r) {
                l = i - k;
                r = i + k;
            }
        }
        vector<int> d2(n);
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
            while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
                k++;
            }
            d2[i] = k--;
            if (i + k > r) {
                l = i - k - 1;
                r = i + k;
            }
        }
        /* End Manacher */
        int index1=n,index2=n;
        for(int i=0;i<n;++i){
            if(n-i==d1[i]){
                index1=i;
                break;
            }
        }
        for(int i=0;i<n;++i){
            if(n-i==d2[i]){
                index2=i;
                break;
            }
        }
        if(index1<index2){
            for(int i=0;i<=index1;++i){
                cout<<s[i];
            }
            for(int i=index1-1;i>=0;--i){
                cout<<s[i];
            }
            cout<<endl;
        }
        else{
            for(int i=0;i<=index2;++i){
                cout<<s[i];
            }
            for(int i=index2-2;i>=0;--i){
                cout<<s[i];
            }
            cout<<endl;
        }
    }
    return 0;
}