python - 构造一个KMP算法要回溯多次的例子

Question

我正在尝试构建一个示例，其中 kmp algorithm computeLPSArray 阶段必须针对某个 i(LPS 阵列中的单元格)多次回溯(参见下面的评论)。

例如对于 'AAACAAA'，它为 i = 3 访问回溯部分两次，为 i = 7

访问一次

你能帮我构造一个字符串，它会为某个 i 访问回溯部分 3-4 次吗？

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

Answer 1

'AAAACAA' 它访问回溯部分 3 次 i = 4。

'AAAAACA' 它访问回溯部分 4 次 i = 5。