给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，形成最大的字典序，返回字典序最大的结果。
1.暴力法。
2.DC3算法。自然智慧想不到，需要练敏感度。
2.1.构造字符串。str = str1+最小字符+str2。
2.2.对str进行dc3算法，求出rank数组。
2.3.遍历0到str1长度，找到小于str2起始位置的序号。
2.4.根据序号算出bestSplit值。时间紧，先放一放。
2.5.根据bestSplit拆分str1，然后合并。返回str1左+str2+str1右。
代码用golang编写。代码如下：
package main
import (
"fmt"
"index/suffixarray"
"math/rand"
"time"
"unsafe"
)
func main() {
rand.Seed(time.Now().Unix())
//YJWBRFKBMYQWFCRTSA
//YTOFNTX
cnt := 0
const TOTAL = 10000
for i := 0; i < TOTAL; i++ {
s1 := newRandString()
s2 := newRandString()
fmt.Println("s1 = ", s1)
fmt.Println("s2 = ", s2)
ret1 := right(s1, s2)
ret2 := maxCombine(s1, s2)
fmt.Println("暴力的答案：", ret1)
fmt.Println("DC3的答案：", ret2)
if ret1 == ret2 {
fmt.Println("正确")
cnt++
} else {
fmt.Println("错误")
}
fmt.Println("-------------")
}
fmt.Println("总数：", TOTAL)
fmt.Println("正确：", cnt)
}
func newRandString() string {
retLen := rand.Intn(20) + 5
ret := make([]byte, retLen)
for i := 0; i < retLen; i++ {
ret[i] = byte(rand.Intn(26) + 'A')
}
return string(ret)
}
func right(s1 string, s2 string) string {
if len(s1) == 0 {
return s2
}
if len(s2) == 0 {
return s1
}
ans := s1 + s2
temp := ""
best := len(s1)
for i := 0; i < len(s1); i++ {
temp = s1[0:i] + s2 + s1[i:]
if temp > ans {
ans = temp
best = i
}
}
fmt.Println("暴力best = ", best)
return ans
}
// 正式方法 O(N+M) + O(M^2)
// N : s1长度
// M : s2长度
func maxCombine(s1 string, s2 string) string {
if len(s1) == 0 {
return s2
}
if len(s2) == 0 {
return s1
}
str1 := []byte(s1)
str2 := []byte(s2)
N := len(str1)
M := len(str2)
min := str1[0]
max := str1[0]
for i := 1; i < N; i++ {
min = getMin(min, str1[i])
max = getMax(max, str1[i])
}
for i := 0; i < M; i++ {
min = getMin(min, str2[i])
max = getMax(max, str2[i])
}
all := make([]byte, N+M+1)
index := 0
for i := 0; i < N; i++ {
all[index] = str1[i] - min + 2
index++
}
all[index] = 1
index++
for i := 0; i < M; i++ {
all[index] = str2[i] - min + 2
index++
}
dc3 := NewFddSa(all)
comp := N + 1
for i := 0; i < N; i++ {
if dc3.Rank[i] < dc3.Rank[comp] {
best := bestSplit(s1, s2, i)
//best := i //这句代码是错的
fmt.Println("DC3的best = ", best)
return s1[0:best] + s2 + s1[best:]
}
}
return s1 + s2
}
func bestSplit(s1 string, s2 string, first int) int {
N := len(s1)
M := len(s2)
end := N
for i, j := first, 0; i < N && j < M; i, j = i+1, j+1 {
if s1[i] < s2[j] {
end = i
break
}
}
bestPrefix := s2
bestSplit := first
for i, j := first+1, M-1; i <= end; i, j = i+1, j-1 {
curPrefix := s1[first:i] + s2[0:j]
if curPrefix >= bestPrefix {
bestPrefix = curPrefix
bestSplit = i
}
}
if bestSplit != first {
fmt.Println("注意，first = ", first, " ,bestSplit = ", bestSplit)
}
return bestSplit
}
func getMax(a byte, b byte) byte {
if a > b {
return a
} else {
return b
}
}
func getMin(a byte, b byte) byte {
if a < b {
return a
} else {
return b
}
}
type FddSa struct {
Sa []int
Rank []int
}
func NewFddSa(bytes []byte) *FddSa {
ret := &FddSa{}
ret.Rank = make([]int, len(bytes))
ret.Sa = make([]int, len(bytes))
index := suffixarray.New(bytes)
p1 := uintptr(unsafe.Pointer(index)) //获取指针
p1 += 24
p2 := *(*[]int32)(unsafe.Pointer(p1)) //将指针转行成切片
for i := 0; i < len(bytes); i++ {
ret.Sa[i] = int(p2[i]) //sa数组
ret.Rank[int(p2[i])] = i //rank数组
}
return ret
}执行结果如下：
