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 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

}

执行结果如下：

---

左神java代码

评论

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