-
Notifications
You must be signed in to change notification settings - Fork 2
/
214.cpp
44 lines (41 loc) · 1.23 KB
/
214.cpp
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
class Solution {
public:
vector<int> getSuffix(string& p) {
int n = p.size();
vector<int> suffix(n, 0);
suffix[0] = 0;
for (int i = 1; i < n; ++i) {
int j = suffix[i - 1];
while (j >= 1 && p[i] != p[j]) {
j = suffix[j - 1];
}
suffix[i] = j + (p[i] == p[j]);
}
return suffix;
}
string shortestPalindrome(string s) {
// B + s: BAA'B'
// => s: AA'B' = pattern
// => revS: BAA' = target
// find longest matched pattern in target
if (s == "") return s;
string pattern = s;
string target = s;
reverse(target.begin(), target.end());
vector<int> suffix = getSuffix(pattern);
int n = target.size();
vector<int> dp(n, 0);
dp[0] = target[0] == pattern[0];
for (int i = 1; i < n; ++i) {
int j = dp[i - 1];
while (j >= 1 && target[i] != pattern[j]) {
j = suffix[j - 1];
}
dp[i] = j + (target[i] == pattern[j]);
}
int length = dp[n - 1];
string B = s.substr(length);
reverse(B.begin(), B.end());
return B + s;
}
};