求字母表{a，b，c}上长度为n的字符串w的个数

Question

我想知道如何计算所有长度为n的字符串的数量，使字符串w的任何长度为4的子字符串，所有三个字母a、b、c都出现。例如，当n=9时，应打印abbcaabca，但不应包括aabbcabac。

我试着做一个类似的数学公式

3^N - 3 * 2^N + 3 or (3^(N-3))*N!

它能这样工作吗？还是我必须生成它们并计数？我正在处理像100这样的大数字，我认为我无法生成它们来计算它们。

Answer 1

您可能应该能够逐步提高，从让我们说出所有长度为4的可能单词开始，然后只添加一个字母，并计算可能允许的结果单词。然后，你可以迭代地达到高数字，而不必探索所有3^N的可能性。

const unsigned w = 4;
unsigned n = 10;
vector<string> before,current;
// obtain all possible permutations of the strings "aabc", "abbc" and "abcc"
string base = "aabc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);
base = "abbc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);
base = "abcc";
before.emplace_back(base);
while(std::next_permutation(base.begin(),base.end())) before.emplace_back(base);
// iteratively add single letters to the words in the collection and add if it is a valid word
size_t posa,posb,posc;
for (unsigned k=1;k<n-w;++k)
{
    current.clear();
    for (const auto& it : before)
    {
        posa = it.find("a",k);
        posb = it.find("b",k);
        posc = it.find("c",k);
        if (posb!= string::npos && posc!= string::npos) current.emplace_back(it+"a");
        if (posa!= string::npos && posc!= string::npos) current.emplace_back(it+"b");
        if (posa!= string::npos && posb!= string::npos) current.emplace_back(it+"c");
    }
    before = current;
}
for (const auto& it : current) cout<<it<<endl;
cout<<current.size()<<" valid words of length "<<n<<endl;

注意，有了这个，你仍然会很快遇到指数墙。。。在一个更有效的实现中，我会将单词表示为整数（不是整数的向量，而是基数为3的整数表示），但指数缩放仍然存在。如果你只是对数字感兴趣，@Jeffrey的方法肯定会更好。

Answer 2

诀窍是分解问题。考虑：

知道有多少这样的字符串，长度为50，以每对字母结尾，会有帮助吗？

50个字符串的数目，以AA次结束50个字符串的数目，以B或C开头+50个字符串的数目，以AB次结束50字符串的编号，以C开头+所有其他组合都提供了100个长字符串的数量。

继续递归地分解它。

查找动态编程。

还可以查找大量的库。