2023-08-18：用go写算法。你会得到一个字符串 text，你应该把它分成 k 个子字符串 (subtext1, subt

福大大架构师每日一题

发布于 2023-08-29 10:46:11

1970

发布于 2023-08-29 10:46:11

文章被收录于专栏：福大大架构师每日一题

2023-08-18：用go写算法。你会得到一个字符串 text，

你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk)。

要求满足:

subtexti 是非空字符串，

所有子字符串的连接等于 text ，

( 即subtext1 + subtext2 + ... + subtextk == text )，

subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k )。

返回k可能最大值。

输入：text = "ghiabcdefhelloadamhelloabcdefghi"。

输出：7。

解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

来自小红书、谷歌、Bloomberg、微软、亚马逊、字节跳动、摩根大通、Uber。

来自左程云。

答案2023-08-18：

这两种算法的步骤可以概括如下：

方法1：longestDecomposition1(text)

1.初始化变量 s 为文本的字节数组，变量 n 为文本长度，变量 l 和 r 分别指向字节数组的开头和末尾，变量 ans 初始化为 0。

2.使用双指针法，当 l 小于等于 r 时进行循环：

• 初始化变量 size 为 1。
• 在一个循环内，通过比较子字符串是否相同来确定 size 的值，直到 size 使得剩余的子字符串无法再被分割为相同的子字符串。
• 如果 size 使得剩余的子字符串可以被分割为相同的子字符串，则将 ans 增加 2。
• 向右移动 l 和向左移动 r，使其分别指向剩余子字符串的新开头和新结尾。

3.如果 r 恰好等于 l-1，则返回 ans，否则返回 ans + 1。

方法2：longestDecomposition2(text)

1.初始化变量 s 为文本的字节数组，变量 n 为文本长度，通过调用 generateDC3 函数生成 dc3 结构体。

2.初始化变量 rank 为 dc3 结构体中的 Rank 切片，初始化变量 rmq 为通过调用 NewRMQ 函数生成的 RMQ 结构体，变量 l 和 r 分别指向字节数组的开头和末尾，变量 ans 初始化为 0。

3.使用双指针法，当 l 小于等于 r 时进行循环：

• 初始化变量 size 为 1。
• 在一个循环内，通过比较子字符串是否相同来确定 size 的值，直到 size 使得剩余的子字符串无法再被分割为相同的子字符串。
• 如果 size 使得剩余的子字符串可以被分割为相同的子字符串，则将 ans 增加 2。
• 向右移动 l 和向左移动 r，使其分别指向剩余子字符串的新开头和新结尾。

4.如果 r 恰好等于 l-1，则返回 ans，否则返回 ans + 1。

复杂度分析：

最初的算法longestDecomposition1的时间复杂度和空间复杂度如下：

• 时间复杂度：O(n^2)，其中n为输入字符串text的长度。
• 空间复杂度：O(n)，需要额外的空间来存储中间计算结果。

优化后的算法longestDecomposition2使用了DC3和RMQ的数据结构，并进行了分块处理，因此时间复杂度和空间复杂度如下：

• 时间复杂度：O(n log n)，其中n为输入字符串text的长度。
• 空间复杂度：O(n)，需要额外的空间来存储中间计算结果。

总结：优化后的算法longestDecomposition2虽然时间复杂度更低，但空间复杂度和初次计算的算法longestDecomposition1相同，都为O(n)。

go语言完整代码如下：

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("性能测试结束")
}