2021-04-03：给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，

2021-04-03：给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，形成最大的字典序，返回字典序最大的结果。

福大大答案2021-04-03：

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 mainimport (    "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}

执行结果如下：

左神java代码
评论

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

你的鼓励让我更有动力

赞赏

0人进行了赞赏支持

你的鼓励让我更有动力

更多相关文章

随机推荐