Contents

Problem

題目網址

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

Solution

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

原字串 S: xyzxyz  
反轉 R:   zyxzyx

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

Code

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<cstring>
#include<algorithm>
#< 大专栏  UVa 11475 - Extend to Palindromespan class="meta-keyword">define N 100001