2023-05-21：给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个， 并把它加到字符串的末尾。 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串。 输入：s

package main

import (
	"fmt"
	"sort"
	"strings"
)

func orderlyQueue(s string, k int) string {
	if k > 1 {
		sArr := strings.Split(s, "")
		sort.Strings(sArr)
		return strings.Join(sArr, "")
	} else {
		s2 := s + s
		n := len(s2)
		arr := make([]int, n)
		for i := 0; i < n; i++ {
			arr[i] = int(s2[i] - 'a' + 1)
		}
		dc3 := NewDC3(arr, 26)
		n = n >> 1
		minRankIndex := 0
		for i := 1; i < n; i++ {
			if dc3.rank[i] < dc3.rank[minRankIndex] {
				minRankIndex = i
			}
		}
		return s[minRankIndex:] + s[0:minRankIndex]
	}
}

// DC3算法实现
// 根据原算法Java代码修改
type DC3 struct {
	sa   []int
	rank []int
}

// NewDC3 构造函数
func NewDC3(nums []int, max int) *DC3 {
	dc3 := &DC3{}
	dc3.sa = dc3.sa0(nums, max)
	dc3.rank = dc3.rank0()
	return dc3
}

func (dc3 *DC3) sa0(nums []int, K int) []int {
	n := len(nums)
	arr := make([]int, n+3)
	copy(arr, nums)
	return dc3.skew(arr, n, K)
}

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 nums[sa12[i]] != c0 || nums[sa12[i]+1] != c1 || nums[sa12[i]+2] != c2 {
			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)

	sa := make([]int, n)
	for p, t, k := 0, n0-n1, 0; k < n; k++ {
		i := sa12[t]
		if i < n0 {
			i = i*3 + 1
		} else {
			i = (i-n0)*3 + 2
		}
		j := sa0[p]
		if i < n-1 && j < n-1 {
			if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i+1] < nums[j+1]) ||
				(nums[i] == nums[j] && nums[i+1] == nums[j+1] && nums[i+2] <= nums[j+2]) {
				sa[k] = i
				t++
				if t == n02 {
					k++
					for ; p < n0; p++ {
						sa[k] = sa0[p]
						k++
					}
				}
			} else {
				sa[k] = j
				p++
				if p == n0 {
					k++
					for ; t < n02; t++ {
						i := sa12[t]
						if i < n0 {
							sa[k] = i*3 + 1
						} else {
							sa[k] = (i-n0)*3 + 2
						}
						k++
					}
				}
			}
		} else {
			if nums[i] < nums[j] || (nums[i] == nums[j] && nums[i+1] <= nums[j+1]) {
				sa[k] = i
				t++
				if t == n02 {
					k++
					for ; p < n0; p++ {
						sa[k] = sa0[p]
						k++
					}
				}
			} else {
				sa[k] = j
				p++
				if p == n0 {
					k++
					for ; t < n02; t++ {
						i := sa12[t]
						if i < n0 {
							sa[k] = i*3 + 1
						} else {
							sa[k] = (i-n0)*3 + 2
						}
						k++
					}
				}
			}
		}
	}
	return sa
}

func (dc3 *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 (dc3 *DC3) rank0() []int {
	n := len(dc3.sa)
	ans := make([]int, n)
	for i := 0; i < n; i++ {
		ans[dc3.sa[i]] = i
	}
	return ans
}

func main() {
	s := "baaca"
	k := 3
	result := orderlyQueue(s, k)
	fmt.Println(result)
}