为什么该Python字符串统计程序对部分输入会进入无限循环

问题描述 #

给定3个字符串S1、S2和X，求满足以下条件的不同有序字符串对(P,Q)的数量：

1. P+Q是X的子串；
2. P是S1的任意前缀（可空）；
3. Q是S2的任意前缀（可空）。
   注：子串指字符串的连续子序列，空字符串是任意字符串的子串与前缀。

实现代码 #

for _ in range(int(input())):
    s1,s2,x=input(),input(),input()
    l=[]
    c=1
    a=0
    k=0
    while(k<len(s1)):
        if(s1[0:k+1] in x):
            a+=1
            k+=1
            print(s1[0:k])
            l.append((s1[0:k],""))
    b=0
    k=0
    while(k<len(s2)):
        if(s2[0:k+1] in x):
            b+=1
            k+=1
            print(s2[0:k])
            l.append(("",s2[0:k]))
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[0:i+1]+s2[0:j+1] in x and (s1[0:i+1],s2[0:j+1]) not in l:
                c+=1
                l.append((s1[0:i+1],s2[0:j+1]))
                print(s1[0:i+1]+s2[0:j+1])
                print(i,j)
    print(a+b+c)
    #print(a)
    #print(b)
    #print(c)

异常情况 #

上述代码大部分测试用例运行正常，三组测试用例预期输出为7、4、11，其中：

• 输入S1=ab、S2=bc、X=abc，运行正常；
• 输入S1=aab、S2=acb、X=bcaabacbc，运行正常；
• 输入S1=aa、S2=bb、X=ab时，程序进入无限循环无输出。

死循环原因 #

代码中统计S1、S2符合要求的前缀的两个while循环存在逻辑漏洞：
循环内只有当当前前缀s1[0:k+1]存在于X中时，才会执行k+=1操作，若前缀不存在于X中，k的值不会变化，永远满足k<len(s1)的循环条件，导致循环无限执行。

以异常测试用例为例：
S1值为aa，长度为2，当k=0时，前缀a存在于X=ab中，k递增到1；下一轮循环判断前缀aa，不存在于X中，k始终保持为1，永远小于2，程序卡在该循环无法继续执行。S2的统计循环存在完全相同的问题。

内容的提问来源于stack exchange，提问作者Abhishek Sanwal