2023-08-18: Write algorithms in go. You will get a string text, you should split it into k substrings (subtext1, subtext2, …, subtextk). Requirements met: subtexti yes

2023-08-18: Write algorithms in go. you will get a string text,

You should split it into k substrings (subtext1, subtext2, …, subtextk).

Requirements meet:

subtexti is a non-empty string,

concatenation of all substrings equals text ,

(i.e. subtext1 + subtext2 + … + subtextk == text),

subtexti == subtextk – i + 1 means all valid values of i (i.e. 1 <= i <= k).

Returns the k possible maximum value.

Input: text = “ghiabcdefhelloadamhelloabcdefghi”.

Output: 7.

Explanation: We can split the string into “(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)”.

From Xiaohongshu, Google, Bloomberg, Microsoft, Amazon, ByteDance, JPMorgan Chase, and Uber.

From Zuo Chengyun.

Answer 2023-08-18:

The steps of these two algorithms can be summarized as follows:

Method 1: longestDecomposition1(text)

1. Initialize the variable s as the byte array of text, the variable n as the text length, and the variables l and r Point to the beginning and end of the byte array respectively, and the variable ans is initialized to 0.

2. Use the double pointer method to loop when l is less than or equal to r:

• Initialize variable size to 1.

• Within a loop, the value of size is determined by comparing whether the substrings are the same, until size makes the remaining substrings no longer split into identical substrings. .

• If size is such that the remaining substrings can be split into identical substrings, increase ans by 2.

• Move l to the right and r to the left so that they point to the new beginning and end of the remaining substring respectively.

3. If r is exactly equal to l-1, return ans, otherwise return ans + 1.

Method 2: longestDecomposition2(text)

1. Initialize the variable s to be the byte array of the text, the variable n to be the length of the text, and generate dc3generateDC3 function. code> structure.

2. Initialize the variable rank to be the Rank slice in the dc3 structure, and initialize the variable rmq to be by calling NewRMQ function generates the RMQ structure. The variables l and r point to the beginning and end of the byte array respectively. The variables ans is initialized to 0.

3. Use the double pointer method to loop when l is less than or equal to r:

• Initialize variable size to 1.

• Within a loop, the value of size is determined by comparing whether the substrings are the same, until size makes the remaining substrings no longer split into identical substrings. .

• If size is such that the remaining substrings can be split into identical substrings, increase ans by 2.

• Move l to the right and r to the left so that they point to the new beginning and end of the remaining substring respectively.

4. If r is exactly equal to l-1, return ans, otherwise return ans + 1.

Complexity Analysis:

The time complexity and space complexity of the original algorithm longestDecomposition1 are as follows:

• Time complexity: O(n^2), where n is the length of the input string text.

• Space complexity: O(n), additional space is required to store intermediate calculation results.

The optimized algorithm longestDecomposition2 uses the data structures of DC3 and RMQ and performs block processing, so the time complexity and space complexity are as follows:

• Time complexity: O(n log n), where n is the length of the input string text.

• Space complexity: O(n), additional space is required to store intermediate calculation results.

Summary: Although the time complexity of the optimized algorithm longestDecomposition2 is lower, the space complexity is the same as the initial calculation algorithm longestDecomposition1, which is O(n).

The complete code of go language is as follows:

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 := & amp;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 & amp; & amp; a2 <= b2)
}

func (t *DC3) leq(a1 int, a2 int, a3 int, b1 int, b2 int, b3 int) bool {<!-- -->
return a1 < b1 || (a1 == b1 & amp; & amp; 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 & amp; & amp; j + k < n & amp; & amp; 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 := & amp;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("First show the usage of DC3")
test := "aaabaaa"
dc3 := generateDC3([]byte(test), len(test))
fmt.Println("sa[i] indicates the suffix string at the beginning of the i-th position in the dictionary order")
sa := dc3.Sa
for i := 0; i < len(test); i + + {<!-- -->
fmt.Printf("%d : %d\\
", i, sa[i])
}

fmt.Println("rank[i] indicates the lexicographical order of the suffix string at the beginning of position i")
rank := dc3.Rank
for i := 0; i < len(test); i + + {<!-- -->
fmt.Printf("%d : %d\\
", i, rank[i])
}

fmt.Println("height[i] indicates the suffix string of lexicographic ranking i and the suffix string of the previous ranking, how long is the longest common prefix")
height := dc3.Height
for i := 0; i < len(test); i + + {<!-- -->
fmt.Printf("%d : %d\\
", i, height[i])
}

fmt.Println("Performance test starts")
var start, end int64
s := generateS(300000, 1)
t := generateT(s, 2)

start = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("The result of method 1:", longestDecomposition1(t))
end = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("The running time of method 1:", end-start, "milliseconds")

start = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("The result of method 2:", longestDecomposition2(t))
end = time.Now().UnixNano() / int64(time.Millisecond)
fmt.Println("The running time of method 2:", end-start, "milliseconds")

fmt.Println("Performance test ended")
}