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

Question

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

例如对于abb b

子串：a，b，b，ab，bb，abb。答案：包含b atlest的字符串= 5。

PS。我通过生成所有子串然后检入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'))

Answer 2

您可以将其转过来并扫描您的字符串以查找您的信件。每当你在某个位置i中发现一个事件时，你知道它包含在包含它的所有子串中（即所有在i之前或之后开始并在i之后或之后结束的子串），所以你只需要存储索引对用于定义子字符串，而不是显式存储子字符串。

话虽如此，你仍然需要这种方法的O（n²），因为虽然你不介意重复的子串，如你的例子所示，你不想两次计算相同的子串，所以你仍然需要确保你不要两次选择同一对指数。

Answer 3

我们将字符串视为abcdaefgabb，将给定字符视为a。

• 通过char循环字符串char。
• 如果一个字符与给定的字符匹配，那么让我们说a在索引4，所以包含a的子串的数量是从abcda到aefgabb。所以，我们添加(4-0 + 1) + (10 - 4) = 11。这些代表子串为abcda，bcda，cda，da，a，ae，aef，aefg，aefga，aefgab和aefgabb。
• 这适用于你找到a的地方，就像你在索引0和索引8找到它一样。
• 最终答案是上述数学运算的总和。

更新：您必须在最后发生的a和当前的a之间保持2个指针，以避免计算以相同索引开始结束的重复子串。

Answer 4

将子字符串视为从字符串中的字母之间的间隙中选择两个元素，并包括它们之间的所有内容（字符串的最末端有间隙）。

对于长度为n的字符串，有选择（n + 1,2）个子串。

其中，对于不包括目标的k个字符的每次运行，选择（k + 1,2）子串仅包括来自该子串的字母。主字符串的所有其他子字符串必须包含目标。

答案：选择（n + 1,2） - sum（选择（k_i + 1,2）），其中k_i是不包括目标的字母的运行长度。