package main
import (
"fmt"
"strings"
"time"
)
func longestDecomposition1(text string) int {
if len(text) == 1 {
return 1
}
s := []byte(text)
n := len(s)
l := 0
r := n - 1
ans := 0
for l <= r {
size := 1
for 2*size <= r-l+1 {
if same1(s, l, r, size) {
break
}
size++
}
if 2*size <= r-l+1 {
ans += 2
}
l += size
r -= size
}
if r == l-1 {
return ans
}
return ans + 1
}
func same1(s []byte, l, r, size int) bool {
for i, j := l, r-size+1; j <= r; i, j = i+1, j+1 {
if s[i] != s[j] {
return false
}
}
return true
}
func longestDecomposition2(str string) int {
if len(str) == 1 {
return 1
}
s := []byte(str)
n := len(s)
dc3 := generateDC3(s, n)
rank := dc3.Rank
rmq := NewRMQ(dc3.Height)
l := 0
r := n - 1
ans := 0
for l <= r {
size := 1
for ; 2*size <= r-l+1; size++ {
if same2(rank, rmq, l, r, size) {
break
}
}
if 2*size <= r-l+1 {
ans += 2
}
l += size
r -= size
}
if r == l-1 {
return ans
}
return ans + 1
}
func same2(rank []int, rmq *RMQ, l, r, size int) bool {
start1 := l
start2 := r - size + 1
minStart := getMin(rank[start1], rank[start2])
maxStart := getMax(rank[start1], rank[start2])
return rmq.Min(minStart+1, maxStart) >= size
}
func getMin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func generateDC3(s []byte, n int) *DC3 {
min0 := 2147483647
max0 := -2147483648
for _, cha := range s {
min0 = getMin(min0, int(cha))
max0 = getMax(max0, int(cha))
}
arr := make([]int, n)
for i := 0; i < n; i++ {
arr[i] = int(s[i]) - min0 + 1
}
return NewDC3(arr, max0-min0+1)
}
type DC3 struct {
Sa []int
Rank []int
Height []int
}
func NewDC3(nums []int, max int) *DC3 {
res := &DC3{}
res.Sa = res.sa(nums, max)
res.Rank = res.rank()
res.Height = res.height(nums)
return res
}
func (dc3 *DC3) sa(nums []int, max int) []int {
n := len(nums)
arr := make([]int, n+3)
copy(arr, nums)
return dc3.skew(arr, n, max)
}
func (dc3 *DC3) skew(nums []int, n int, K int) []int {
n0 := (n + 2) / 3
n1 := (n + 1) / 3
n2 := n / 3
n02 := n0 + n2
s12 := make([]int, n02+3)
sa12 := make([]int, n02+3)
for i, j := 0, 0; i < n+(n0-n1); i++ {
if i%3 != 0 {
s12[j] = i
j++
}
}
dc3.radixPass(nums, s12, sa12, 2, n02, K)
dc3.radixPass(nums, sa12, s12, 1, n02, K)
dc3.radixPass(nums, s12, sa12, 0, n02, K)
name := 0
c0 := -1
c1 := -1
c2 := -1
for i := 0; i < n02; i++ {
if c0 != nums[sa12[i]] || c1 != nums[sa12[i]+1] || c2 != nums[sa12[i]+2] {
name++
c0 = nums[sa12[i]]
c1 = nums[sa12[i]+1]
c2 = nums[sa12[i]+2]
}
if sa12[i]%3 == 1 {
s12[sa12[i]/3] = name
} else {
s12[sa12[i]/3+n0] = name
}
}
if name < n02 {
sa12 = dc3.skew(s12, n02, name)
for i := 0; i < n02; i++ {
s12[sa12[i]] = i + 1
}
} else {
for i := 0; i < n02; i++ {
sa12[s12[i]-1] = i
}
}
s0 := make([]int, n0)
sa0 := make([]int, n0)
for i, j := 0, 0; i < n02; i++ {
if sa12[i] < n0 {
s0[j] = 3 * sa12[i]
j++
}
}
dc3.radixPass(nums, s0, sa0, 0, n0, K)
sasa := make([]int, n)
for p, t, k := 0, n0-n1, 0; k < n; k++ {
i := 0
if sa12[t] < n0 {
i = sa12[t]*3 + 1
} else {
i = (sa12[t]-n0)*3 + 2
}
j := sa0[p]
rr := false
if sa12[t] < n0 {
rr = dc3.leq1(nums[i], s12[sa12[t]+n0], nums[j], s12[j/3])
} else {
rr = dc3.leq(nums[i], nums[i+1], s12[sa12[t]-n0+1], nums[j], nums[j+1], s12[j/3+n0])
}
if rr {
sasa[k] = i
t++
if t == n02 {
for k++; p < n0; p, k = p+1, k+1 {
sasa[k] = sa0[p]
}
}
} else {
sasa[k] = j
p++
if p == n0 {
for k++; t < n02; t, k = t+1, k+1 {
if sa12[t] < n0 {
sasa[k] = sa12[t]*3 + 1
} else {
sasa[k] = (sa12[t]-n0)*3 + 2
}
}
}
}
}
return sasa
}
func (t *DC3) radixPass(nums []int, input []int, output []int, offset int, n int, k int) {
cnt := make([]int, k+1)
for i := 0; i < n; i++ {
cnt[nums[input[i]+offset]]++
}
for i, sum := 0, 0; i < len(cnt); i++ {
t := cnt[i]
cnt[i] = sum
sum += t
}
for i := 0; i < n; i++ {
output[cnt[nums[input[i]+offset]]] = input[i]
cnt[nums[input[i]+offset]]++
}
}
func (t *DC3) leq1(a1 int, a2 int, b1 int, b2 int) bool {
return a1 < b1 || (a1 == b1 && a2 <= b2)
}
func (t *DC3) leq(a1 int, a2 int, a3 int, b1 int, b2 int, b3 int) bool {
return a1 < b1 || (a1 == b1 && t.leq1(a2, a3, b2, b3))
}
func (t *DC3) rank() []int {
n := len(t.Sa)
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[t.Sa[i]] = i
}
return ans
}
func (t *DC3) height(s []int) []int {
n := len(s)
ans := make([]int, n)
for i, k := 0, 0; i < n; i++ {
if t.Rank[i] != 0 {
if k > 0 {
k--
}
j := t.Sa[t.Rank[i]-1]
for i+k < n && j+k < n && s[i+k] == s[j+k] {
k++
}
ans[t.Rank[i]] = k
}
}
return ans
}
type RMQ struct {
min0 [][]int
}
func NewRMQ(arr []int) *RMQ {
res := &RMQ{}
n := len(arr)
k := power2(n)
res.min0 = make([][]int, n+1)
for i := 0; i <= n; i++ {
res.min0[i] = make([]int, k+1)
}
for i := 1; i <= n; i++ {
res.min0[i][0] = arr[i-1]
}
for j := 1; (1 << j) <= n; j++ {
for i := 1; i+(1<<j)-1 <= n; i++ {
res.min0[i][j] = getMin(res.min0[i][j-1], res.min0[i+(1<<(j-1))][j-1])
}
}
return res
}
func (t *RMQ) Min(l, r int) int {
l++
r++
k := power2(r - l + 1)
return getMin(t.min0[l][k], t.min0[r-(1<<k)+1][k])
}
func power2(m int) int {
ans := 0
for (1 << ans) <= (m >> 1) {
ans++
}
return ans
}
func generateS(a, b int) string {
ans := make([]byte, a+b)
for i := 0; i < a; i++ {
ans[i] = 'a'
}
for i, j := a, 0; j < b; i, j = i+1, j+1 {
ans[i] = 'b'
}
return string(ans)
}
func generateT(part string, n int) string {
builder := strings.Builder{}
for i := 0; i < n; i++ {
builder.WriteString(part)
}
return builder.String()
}
func main() {
fmt.Println("先展示一下DC3的用法")
test := "aaabaaa"
dc3 := generateDC3([]byte(test), len(test))
fmt.Println("sa[i]表示字典序排名第i的是什么位置开头的后缀串")
sa := dc3.Sa
for i := 0; i < len(test); i++ {
fmt.Printf("%d : %d\n", i, sa[i])
}
fmt.Println("rank[i]表示i位置开头的后缀串的字典序排多少名")
rank := dc3.Rank
for i := 0; i < len(test); i++ {
fmt.Printf("%d : %d\n", i, rank[i])
}
fmt.Println("height[i]表示字典序排名i的后缀串和前一个排名的后缀串,最长公共前缀是多长")
height := dc3.Height
for i := 0; i < len(test); i++ {
fmt.Printf("%d : %d\n", i, height[i])
}
fmt.Println("性能测试开始")
var start, end int64
s := generateS(300000, 1)
t := generateT(s, 2)
start = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("方法1的结果 :", longestDecomposition1(t))
end = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("方法1的运行时间 :", end-start, "毫秒")
start = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("方法2的结果 :", longestDecomposition2(t))
end = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("方法2的运行时间 :", end-start, "毫秒")
fmt.Println("性能测试结束")
}
评论