-
Notifications
You must be signed in to change notification settings - Fork 546
/
d.go
55 lines (52 loc) · 923 Bytes
/
d.go
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
package main
// github.com/EndlessCheng/codeforces-go
func checkPartitioning(s string) (ans bool) {
var maxLen []int
manacher := func(origin []byte) {
n := len(origin)
m := 2*n + 2
s := make([]byte, m+1)
s[0] = '^'
for i, c := range origin {
s[2*i+1] = '#'
s[2*i+2] = c
}
s[2*n+1] = '#'
s[2*n+2] = '$'
maxLen = make([]int, m+1)
mid, r := 0, 0
for i := 2; i < m; i++ {
mx := 1
if i < r {
mx = min(maxLen[2*mid-i], r-i)
}
for ; s[i-mx] == s[i+mx]; mx++ {
}
if i+mx > r {
mid, r = i, i+mx
}
maxLen[i] = mx
}
}
// [l,r] 0<=l<=r<n
isP := func(l, r int) bool { return maxLen[l+r+2]-1 >= r-l+1 }
manacher([]byte(s))
n := len(s)
for i := 1; i < n-1; i++ {
if !isP(0, i-1) {
continue
}
for j := i; j < n-1; j++ {
if isP(i, j) && isP(j+1, n-1) {
return true
}
}
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}