2023-08-18：用go寫算法。你會得到一個字符串 text，

你應(yīng)該把它分成 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、微軟、亞馬遜、字節(jié)跳動、摩根大通、Uber。

來自左程云。

答案2023-08-18：

這兩種算法的步驟可以概括如下：

方法1：longestDecomposition1(text)

1.初始化變量?s?為文本的字節(jié)數(shù)組，變量?n?為文本長度，變量?l?和?r?分別指向字節(jié)數(shù)組的開頭和末尾，變量?ans?初始化為 0。

2.使用雙指針法，當(dāng)?l?小于等于?r?時(shí)進(jìn)行循環(huán)：

• ??初始化變量?size?為 1。

• ??在一個循環(huán)內(nèi)，通過比較子字符串是否相同來確定?size?的值，直到?size?使得剩余的子字符串無法再被分割為相同的子字符串。

• ??如果?size?使得剩余的子字符串可以被分割為相同的子字符串，則將?ans?增加 2。

• ??向右移動?l?和向左移動?r，使其分別指向剩余子字符串的新開頭和新結(jié)尾。

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

方法2：longestDecomposition2(text)

1.初始化變量?s?為文本的字節(jié)數(shù)組，變量?n?為文本長度，通過調(diào)用?generateDC3?函數(shù)生成?dc3?結(jié)構(gòu)體。

2.初始化變量?rank?為?dc3?結(jié)構(gòu)體中的?Rank?切片，初始化變量?rmq?為通過調(diào)用?NewRMQ?函數(shù)生成的?RMQ?結(jié)構(gòu)體，變量?l?和?r?分別指向字節(jié)數(shù)組的開頭和末尾，變量?ans?初始化為 0。

3.使用雙指針法，當(dāng)?l?小于等于?r?時(shí)進(jìn)行循環(huán)：

• ??初始化變量?size?為 1。

• ??在一個循環(huán)內(nèi)，通過比較子字符串是否相同來確定?size?的值，直到?size?使得剩余的子字符串無法再被分割為相同的子字符串。

• ??如果?size?使得剩余的子字符串可以被分割為相同的子字符串，則將?ans?增加 2。

• ??向右移動?l?和向左移動?r，使其分別指向剩余子字符串的新開頭和新結(jié)尾。

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

復(fù)雜度分析：

最初的算法longestDecomposition1的時(shí)間復(fù)雜度和空間復(fù)雜度如下：

• ??時(shí)間復(fù)雜度：O(n^2)，其中n為輸入字符串text的長度。

• ??空間復(fù)雜度：O(n)，需要額外的空間來存儲中間計(jì)算結(jié)果。

優(yōu)化后的算法longestDecomposition2使用了DC3和RMQ的數(shù)據(jù)結(jié)構(gòu)，并進(jìn)行了分塊處理，因此時(shí)間復(fù)雜度和空間復(fù)雜度如下：

• ??時(shí)間復(fù)雜度：O(n log n)，其中n為輸入字符串text的長度。

• ??空間復(fù)雜度：O(n)，需要額外的空間來存儲中間計(jì)算結(jié)果。

總結(jié)：優(yōu)化后的算法longestDecomposition2雖然時(shí)間復(fù)雜度更低，但空間復(fù)雜度和初次計(jì)算的算法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的結(jié)果?:",?longestDecomposition1(t))
????end?=?time.Now().UnixNano()?/?int64(time.Millisecond)
????fmt.Println("方法1的運(yùn)行時(shí)間?:",?end-start,?"毫秒")

????start?=?time.Now().UnixNano()?/?int64(time.Millisecond)
????fmt.Println("方法2的結(jié)果?:",?longestDecomposition2(t))
????end?=?time.Now().UnixNano()?/?int64(time.Millisecond)
????fmt.Println("方法2的運(yùn)行時(shí)間?:",?end-start,?"毫秒")

????fmt.Println("性能測試結(jié)束")
}