algorithm - 包含特定字符的给定字符串的子字符串数

Question

计算给定字符串中包含给定字符的子串数量的最有效算法是什么。

例如对于 abb

子串:a, b, b, ab, bb, abb。答案:包含 b 的字符串至少一次 = 5。

附言。我通过生成所有子字符串然后检查 O(n ^ 2) 来解决这个问题。只是想知道是否有更好的解决方案。

Answer 1

让您需要查找带有字符 X 的子串。

从左到右扫描字符串，保留最后一个 X 的位置:lastX，起始值为 -1

当你在位置 i 遇到 X 时，将 i+1 添加到结果中并更新 lastX
(这是以当前位置结尾的子字符串的数量，它们都包含 X)

当你遇到另一个角色时，将lastX + 1添加到结果
(这也是以当前位置结束并包含 X 的子串数)，
因为子串最右边的可能开始是最后一个 X 的位置

算法是线性的。
示例:

a X a a X a
            good substrings                            overall     
idx  char   ending at idx             lastX   count    count
 0    a      -                        -1       0        0  
 1    X     aX X                       1       2        2 
 2    a     aXa Xa                     1       2        4
 3    a     aXaa Xaa                   1       2        6 
 4    X     aXaaX XaaX aaX aX X        4       5        11 
 5    a     aXaaXa XaaXa aaXa aXa Xa   4       5        16 

Python代码:

def subcnt(s, c):
    last = -1
    cnt = 0
    for i in range(len(s)):
        if s[i] == c:
            last = i
        cnt += last + 1
    return cnt

print(subcnt('abcdba', 'b'))