在python中包含有限字母表上的子字符串的字符串组合

Question

假设我们有一个20个字母的字母表。另外，假设我们有以下子串CCAY。我想计算长度N字母并包含特定子字符串的单词数。你知道吗

更准确地说，如果N=6，我希望以下组合CCAYxx，xCCAYx，xxCCAY，其中x是字母表中的任何字母。如果N=7，组合调整如下CCAYxxx、xCCAYxx、xxCCAYx、xxxCCAY等。你知道吗

此外，我可以认为，当子串仅由字母表中的一个字母组成时存在一个陷阱，例如CCCC，这意味着在N=6的情况下，字符串CCCC不应被多次计数。你知道吗

我将感谢任何帮助或指导如何处理这个问题。任何python中的示例代码都将受到高度赞赏。你知道吗

Answer 1

你说暴力没问题，所以我们开始吧：

alphabet = 'abc'
substring = 'ccc'
n = 7

res = set()
for combination in itertools.product(alphabet, repeat=n-len(substring)):
    # get the carthesian product of the alphabet such that we end up 
    # with a total length of 'n' for the final combination
    for idx in range(len(combination)+1):
        res.add(''.join((*combination[:idx], substring, *combination[idx:])))
print(len(res))

印刷品：

295

对于一个没有重复的子串，比如abc，我得到了396，所以我假设它适当地覆盖了角大小写。你知道吗

毫无疑问，这样做效率低下，足以让数学家们哭泣，但只要你的问题篇幅很小，就应该完成这项工作。你知道吗

---

分析方法

组合的最大数目通过长度n的唯一有序组合的方式给出，给定len(alphabet) = k符号，即k^n。此外，“子串”可以在任意点插入到组合中，这导致总最大值(n+1)*k^n。后者仅在子串在任何一点上都不产生完全相同的最终组合时成立，这使得这个问题很难解析计算。所以，模糊的答案是your result will be somewhere between k^n and (n+1)*k^n。你知道吗

若要在子环的最终组合中包含相同的子环数，则可以按子环的最终组合数进行计数：

n = 6
pre_prod = 'abab'
sub = 'ab'
pre_prods = ['ababab', 'aabbab', 'ababab', 'abaabb', 'ababab']
prods = ['ababab', 'aabbab', 'abaabb']
# len(pre_prodd) - pre_prod.count(sub) -> len(prods) aka 5 - 2 = 3

我看看能不能找到一个公式。。不久的某个时候。你知道吗