Problem Solving►UVa

UVa 11475 - Extend to Palindrome

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

在後面接上最少的字元，使得原來的字串為回文。

Solution

利用原字串和其反轉字串，做 KMP 加速配對過程，找出原字串和反轉後的匹配可以配對到哪，輸出原字串後，再將無法配對完成的反轉字串輸出。

原字串 S: xyzxyz  
反轉 R:   zyxzyx

只能完成一個配對 S[5] 和 R[0]，所以此時先輸出原字串: xyzxyz。
再接上剩餘未配對的 R: yxzyx。
答案為: xyzxyzyxzyx。

Code

UVa 11475UVa 11475 - Extend to Palindrome
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100001
int main()
{
    char str[N], rev[N];
    while (gets(str))
    {
        int fail[N] = { -1 }, len = strlen(str), i, j;
        std::reverse_copy(str, str + len, rev);
        
        //rev's failure function
        for (i = 1, j = -1; i < len; ++i)
        {
            while (j >= 0 && rev[j + 1] != rev[i])
                j = fail[j];
            if (rev[j + 1] == rev[i])
                ++j;
            fail[i] = j;
        }

        //匹配
        for (i = 0, j = -1; i < len; ++i)
        {
            while (j >= 0 && rev[j + 1] != str[i])
                j = fail[j];

            if (rev[j + 1] == str[i])
                ++j;
        }

        for (i = 0; i < len; ++i)
            putchar(str[i]);
        for (++j; j < len; ++j)
            putchar(rev[j]);
        putchar('\n');
    }

    return 0;
}