python - 至少包含一次字符 X 的子字符串的计数。例如输入：str = “abcd”，X = 'b' 输出：6

Question

这个问题是在考试中提出的，但我的代码（如下所示）在 7 个案例中仅通过了 2 个案例。

输入格式：单行输入，逗号分隔

输入：str = “abcd,b”</p>

输出：6

“ab”、“abc”、“abcd”、“b”、“bc”和“bcd”是必需的子字符串。

def slicing(s, k, n):
    loop_value = n - k + 1
    res = []
    for i in range(loop_value):
        res.append(s[i: i + k])

    return res


x, y = input().split(',')
n = len(x)
res1 = []
for i in range(1, n + 1):
    res1 += slicing(x, i, n)

count = 0
for ele in res1:
    if y in ele:
        count += 1

print(count)

标签： pythonpython-3.xlist

Answer 1

当在 stringts中找到目标字符串 ( ) 时S，您可以通过将目标之前的字符数乘以目标之后的字符数（每边加一个）来计算包含该实例的子字符串的数量。

这将涵盖包含目标字符串此实例的所有子字符串，只留下“之后”部分进行进一步分析，您可以递归地进行分析。

def countsubs(S,ts):
    if ts not in S: return 0                   # shorter or no match
    before,after = S.split(ts,1)               # split on target
    result = (len(before)+1)*(len(after)+1)    # count for this instance
    return result + countsubs(ts[1:]+after,ts) # recurse with right side


print(countsubs("abcd","b")) # 6

这将适用于单字符和多字符目标，并且比逐一检查子字符串的所有组合运行得更快。