给定一个长度为n的字符串's'，计算s的一个字符'c'在s的所有子串中出现的次数

Question

考虑字符串 aba。

它的所有子字符串是：[a,b,a,ab,ba,aba]。

在上面的列表中，字符'a'出现了6次，b出现了4次。

有计算公式吗？即 s 的一个字符 'c' 在 s 的所有子串中出现的次数

Answer 1

在一个长度为n的字符串中，有n(n+1)/2个子串。

索引 i 处的字符在每个子字符串中出现一次，但以字符 i-1 或之前结束的子字符串以及以字符 i+1 或之后开始的子字符串除外。请注意，这里我只计算索引 i 处字符的特定出现次数。

换句话说：在一个字符串S c T中，S和T是两个子串，c是一个字符，这个字符c 在 S c T 的每个子字符串中出现一次，但在 S 的子字符串和 T.

的子字符串中除外

因此在长度为n的字符串中索引i处的字符出现的子串的个数是：

k_i = n(n+1)/2 - i(i+1)/2 - (n-i-1)(n-i)/2

如果我们扩展、取消项并重构：

k_i = n(n+1)/2 - i(i+1)/2 - (n-i-1)(n-i)/2
k_i = (n(n+1) - i(i+1) - (n-i-1)(n-i)) / 2
k_i = (n²+n -i²-i -n²+ni+in-i²+n-i) / 2
k_i = (2n + 2ni -2i - 2i²) / 2
k_i = n + ni - i - i²
k_i = n(i+1) - i(i+1)
k_i = (i+1) (n-i)

我们可以对所有出现的这个字符求和。在 python 中，这给出了以下函数：

def count_occurences_in_substrings(s, c):
    n = len(s)
    return sum(
        (i + 1) * (n - i)
        for i, a in enumerate(s) if a == c
    )

通过与实际生成子字符串的强力函数进行比较进行测试：

from itertools import combinations

def bruteforce(s, c):
    return ''.join(s[i:j] for i,j in combinations(range(len(s)+1), 2)).count(c)

for s in ['aba', 'abcdefg', 'bcdaefg']:
    k1 = count_occurences_in_substrings(s, 'a')
    k2 = bruteforce(s, 'a')
    print('{:8s}: {:2d},{:2d}'.format(s, k1, k2))
# aba     :  6, 6
# abcdefg :  7, 7
# bcdaefg : 16,16

给定一个长度为n的字符串's'，计算s的一个字符'c'在s的所有子串中出现的次数

Given a string 's' of length n, calculate the number of occurrences of a character 'c' of s in all substrings of s

algorithm

data-structures

formula