python - 构造一个示例，其中KMP算法必须回溯多次

我试图构建一个例子，其中对于某个i（lps数组中的单元格），kmp algorithmcomputeLPSArray阶段必须多次回溯（见下面的注释）。
例如，对于'AAACAAA'它访问回溯部分两次对于i = 3和一次对于i = 7
你能帮我构造一个字符串，在这里它将访问回溯部分3-4次，用于某个i？

def computeLPSArray(pat, M, lps):
    len = 0 # length of the previous longest prefix suffix
    lps[0]=0 # lps[0] is always 0
    i = 1
    while i < M:
    if pat[i]==pat[len]:
        len+=1
        lps[i] = len
        i+=1
    else:
        if len!=0:
            # backtrack section - When will we get here 3-4 times for the same i???
            len = lps[len-1]
        else:
            lps[i] = 0
            i+=1

最佳答案

对于'AAAACAA'，它会访问3次backtrack部分。
对于i = 4，它会访问4次backtrack部分。

关于python - 构造一个示例，其中KMP算法必须回溯多次，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37498272/