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

福大大架构师每日一题 · · 472 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案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
}

执行结果如下：