查找不包含特定字符串的所有组合

Question

有没有办法找到不包含特定子字符串的数组的所有组合？ 例如 a=['a','b','c'] aaa aab aac aba abb ... ccc

但是我不想要子字符串ab所以aaa aac aca acb ... ccc 我使用下面的代码，但是对于20字符和13的组合，需要花费太多的时间

import itertools

lista=[]
def foo(l):
    yield from itertools.product(*([l] * 3)) 

non=["ab"]

for x in foo('abc'):
    x=(''.join(x))
    for j in non:
        if j in x:
            value=1
            break
        else:
            value=0
    if (value==0):
        lista.append(x)

Answer 1

与其生成所有字符串，然后拒绝包含任何禁止子字符串的字符串，不如（渐进地）通过回溯来构建字符串，并拒绝已经包含禁止子字符串的任何部分字符串。我们只需要测试当前部分字符串是否以任何禁止的子字符串结尾，这比测试是否包含一个子字符串要快

下面是一个使用递归生成器函数的实现：

def strings_without(alphabet, k, avoid):
    def helper(s):
        if any(s.endswith(t) for t in avoid):
            pass
        elif len(s) == k:
            yield s
        else:
            for c in alphabet:
                yield from helper(s + c)
    return helper('')

例如：

>>> for s in strings_without('abc', 3, ['ab']):
...     print(s)
... 
aaa
aac
aca
acb
acc
baa
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cac
cba
cbb
cbc
cca
ccb
ccc

对于大小为20的字母表中长度为13的字符串，这应该是一个很大的改进，但是20¹³是一个巨大的数字。因此，除非你禁止很多子字符串，否则解决方案的数量将非常大。任何算法都不可能在少于O（hk）的时间内生成长度为k的h字符串，因此任何有效算法的运行时间仍然是output-sensitive