计算恰好一次包含给定单词的固定长度字符串的数量

Question

例如，给定固定长度 N=10 和单词 W="radar"。我们也知道我们有 26 个字符。

然后我们可以“轻松”计算出字符串的数量：

radar _ _ _ _ _ -> 26^5-26-1（因为radarradar和radaradar_不行）

_ 雷达 _ _ _ _ -> 26^5-26

_ _ 雷达 _ _ _ -> 26^5

_ _ _ 雷达 _ _ -> 26^5

_ _ _ _ 雷达 _ -> 26^5-26

_ _ _ _ _ 雷达 -> 26^5-26-1

也就是71288150，有没有更好的方法来计算这个？甚至，如果N可以很大。

Answer 1

这个答案主要基于 software engineering stack thread 问一个相关问题，这个问题本身是基于 KMP 算法的。

想法是构建一个确定性有限自动机 (DFA)，其转换是小写字母，可以编码属性匹配模式零、一或2 次以上。例如，对于 pattern = 'radar'，我们的模式长度 n 为 5，因此我们的 中总共有 n + n + 1 个状态DFA.将这些视为 3 行状态会很有帮助：

行0、列i是对应于0个完全匹配的状态，最后i个字母来自我们当前的部分匹配。
行1、列i是对应于1完全匹配的状态，最后i个字母来自我们当前的部分匹配。
行 2 有一个无法转义的状态：我们已经看到至少 2 个完全匹配。

我们的 'row' 只会增加。在代码中，实际上只有一个 2n+1 状态的平面列表，但这只是一个实现细节。

显示了 'radar' 的 DFA 图的部分图：几乎所有的边都没有画出来，因为每个状态都有 26 向外转移。通常最多两个转换不会导致行开始处的 'mismatch' 状态（此处为 0 和 5），但我也不能包括一些后边，其中networkx 会将它们绘制重叠。

为了得到答案，我们需要计算在看到length = 10个字母后处于每种可能状态（从0开始）的频率——好的状态是n, n+1 ... 2n-1，对应于完全匹配。要生成转换矩阵，我们可以使用 KMP 算法中的前缀函数，几乎无需修改。第一行DFA的定义如下：

For state 0 <= i < n,
DFA[i][letter] = Length of longest suffix of (pattern[:i]+letter)
                 that is also a prefix of pattern

需要注意的是，状态 n-1 中的完全匹配将我们移动到第 1 行。状态 n <= i < 2n 的定义相同，只是每个状态向上移动 n .

使用 numpy，我们可以相当快地使用矩阵幂得到答案：我们需要将一个大致 2nx2n 矩阵乘以我们固定的 length 的幂。如果 length 太大，您要么需要使用 Python 的大整数，要么取模以避免溢出，一旦答案变得太大。但是，可以使用朴素矩阵乘法对 O(n^3 * log(length)) 的时间复杂度进行重复平方来完成矩阵求幂。

def kmp_count(pattern: str, length: int) -> int:
    if not pattern.islower():
        raise ValueError("Pattern must be lowercase")

    n = len(pattern)

    if n > length:
        return 0
    if n == length:
        return 1
    if n == 1:
        return length * pow(25, length - 1)

    pattern_chars = [ord(x) - ord('a') for x in pattern]

    # Create the DFA
    dfa = [[0 for _ in range(26)] for _ in range(2 * n + 1)]

    # Final failure state is an absorbing state
    dfa[2 * n] = [2 * n for _ in range(26)]

    dfa[0][pattern_chars[0]] = 1
    restart_state = 0
    for i in range(1, n):
        dfa[i] = dfa[restart_state][:]

        dfa[i][pattern_chars[i]] = i + 1
        restart_state = dfa[restart_state][pattern_chars[i]]

    dfa[n - 1][pattern_chars[n - 1]] += restart_state

    for i in range(n, 2 * n):
        dfa[i] = [x + n for x in dfa[i - n]]

    # Two or more matches moves us to fail state
    dfa[2 * n - 1][pattern_chars[n - 1]] = 2 * n

    transitions = np.zeros((2 * n + 1, 2 * n + 1), dtype=np.int64)
    for i, x in enumerate(dfa):
        for y in x:
            transitions[i][y] += 1

    final_transitions = np.linalg.matrix_power(transitions, length)
    return final_transitions[0, n:2 * n].sum()

print(kmp_count(pattern='radar', length=10))
>>> 71288150

计算恰好一次包含给定单词的固定长度字符串的数量

Calculate the number of fixed-length strings that contain a given word exactly once

python

string

algorithm

combinations

combinatorics