假设我们有一个20个字母的字母表。另外,假设我们有以下子串CCAY。我想计算长度N字母并包含特定子字符串的单词数。你知道吗
更准确地说,如果N=6,我希望以下组合CCAYxx,xCCAYx,xxCCAY,其中x是字母表中的任何字母。如果N=7,组合调整如下CCAYxxx、xCCAYxx、xxCCAYx、xxxCCAY等。你知道吗
此外,我可以认为,当子串仅由字母表中的一个字母组成时存在一个陷阱,例如CCCC,这意味着在N=6的情况下,字符串CCCC不应被多次计数。你知道吗
我将感谢任何帮助或指导如何处理这个问题。任何python中的示例代码都将受到高度赞赏。你知道吗
你说暴力没问题,所以我们开始吧:
印刷品:
对于一个没有重复的子串,比如
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
。你知道吗若要在子环的最终组合中包含相同的子环数,则可以按子环的最终组合数进行计数:
我看看能不能找到一个公式。。不久的某个时候。你知道吗
相关问题 更多 >
编程相关推荐