用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 恢复到其初始状态所需的最短时间。
大体步骤如下：
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))
