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
| unordered_map<double, pair<int, int>> manacher(string A) {
string s = "#";
for(auto ch : A) {
s.push_back(ch);
s.push_back('#');
}
int l = -1, r = 0, n = s.length();
vector<int> dp(n);
for(int i = 0; i < n; i++) {
dp[i] = max(0, min(r - i, r + l - i >= 0 ? dp[r+l-i] : -1));
while(i - dp[i] >= 0 and i + dp[i] < n and s[i-dp[i]] == s[i+dp[i]]) dp[i]++;
if(i + dp[i] > r) {
r = i + dp[i];
l = i - dp[i];
}
}
unordered_map<double, pair<int, int>> res;
auto pos = [](int n) {return n / 2;};
for(int i = 0; i < n; i++) {
int l = i - dp[i] + 1, r = i + dp[i] - 1;
if(s[i] == '#' and l == r) continue;
if(s[l] == '#' and s[r] == '#') l++,r--;
res[(pos(l)+pos(r))/2.] = {pos(l), pos(r)};
}
return res;
}
void helper(vector<vector<string>>& res, string& A, vector<string>& now, unordered_map<double, pair<int, int>>& pal, int p) {
if(p == A.length()) res.push_back(now);
else {
string s = "";
for(int i = p; i < A.length(); i++) {
s.push_back(A[i]);
int l = p, r = i;
double mid = (l + r) / 2.;
if(!pal.count(mid)) continue;
auto [pl, pr] = pal[mid];
if(pl > l or pr < r) continue;
now.push_back(s);
helper(res,A,now,pal,i + 1);
now.pop_back();
}
}
}
vector<vector<string>> Solution::partition(string A) {
unordered_map<double, pair<int, int>> pal = manacher(A);
vector<vector<string>> res;
helper(res, A, vector<string>() = {}, pal, 0);
return res;
}
|
