2024-07-03：用go语言，给定一个初始字符串 word 和一个整数 k，

我们需要按照以下规则进行操作：

每秒钟执行两个操作，即删除word的前k个字符并在末尾添加k个任意字符，直到word恢复到初始状态为止。

我们需要计算恢复到初始状态所需的最短时间，该时间必须大于零。

输入：word = “abacaba”, k = 3。

输出：2。

解释：

第 1 秒，移除 word 的前缀 “aba”，并在末尾添加 “bac” 。因此，word 变为 “cababac”。

第 2 秒，移除 word 的前缀 “cab”，并在末尾添加 “aba” 。因此，word 变为 “abacaba” 并恢复到始状态。

可以证明，2 秒是 word 恢复到其初始状态所需的最短时间。

答案2024-07-03：

chatgpt

题目来自leetcode3029。

大体步骤如下：

1.我们首先定义初始字符串 word 为 “abacaba”，整数 k 为 3。

2.定义函数 minimumTimeToInitialState(s string, k int) int 来计算恢复到初始状态所需的最短时间。

3.在函数内部，我们首先获取字符串 s 的长度 n，并创建一个长度为 n 的整型切片 z 用来存储计算结果。

4.使用循环遍历字符串 s，对每个位置进行处理，维护指针 l 和 r 指示当前处理的子字符串范围。

5.进行 Z-Algorithm 的计算，在内循环中计算以每个位置 i 结尾的最长公共前后缀长度。

6.如果当前位置 i 是步长 k 的倍数且该位置的最长公共前后缀长度 z[i] 大于等于 n-i，说明此时已经恢复到初始状态，返回恢复所需的时间。

7.循环结束后，如果未在合适位置返回恢复时间，则计算总的时间复杂度和额外空间复杂度。

总的时间复杂度为 O(n) 或 O(N+k)，其中 N 是字符串的长度，k 是指定的整数。

在空间复杂度上，除了存储输入数据外，额外使用了长度为 n 的整型切片 z，因此总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

import (
	"fmt"
)

func minimumTimeToInitialState(s string, k int) int {
	n := len(s)
	z := make([]int, n)
	for i, l, r := 1, 0, 0; i < n; i++ {
		if i <= r {
			z[i] = getMin(z[i-l], r-i+1)
		}
		for i+z[i] < n && s[z[i]] == s[i+z[i]] {
			l, r = i, i+z[i]
			z[i]++
		}
		if i%k == 0 && z[i] >= n-i {
			return i / k
		}
	}
	return (n-1)/k + 1
}

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func main() {
	word := "abacaba"
	k := 3
	fmt.Println(minimumTimeToInitialState(word, k))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minimum_time_to_initial_state(s, k):
    n = len(s)
    z = [0] * n
    for i in range(1, n):
        l, r = 0, 0
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            l, r = i, i + z[i]
            z[i] += 1
        if i % k == 0 and z[i] >= n - i:
            return i // k
    return (n - 1) // k + 1

word = "abacaba"
k = 3
print(minimum_time_to_initial_state(word, k))