单词分解算法

Question

假设A是一个有限的字母表，A*是从该字母表中可以组成的所有有限字符串的集合。然后，您将获得一个包含字母表本身（A）和一个属于A*的字符串S的一些字符串的集合F（通常比A*小得多）。

是否有一个多项式时间算法来查找用属于F的字符串的术语对S进行最小分解？

通过分解，我指的是将S = F₁...F_k写成连接的字符串F_j的写作，并尝试最小化数量k。

- barmanthewise

Answer 1

我们可以使用动态规划在多项式时间内解决这个问题，具体如下。

令 D[i] 为你的字符串 S 的前 i 个字符的最小分解。

如果 n 是 S 的长度，f 是 F 中所有字符串的总长度，则我们可以通过迭代 i 来在 O(n.f) 的时间内计算 D。

对于每个 i 值，我们尝试 F 中所有选择作为字符串结尾的可能性，并选择导致最小分解的那一个。

完成以上步骤后，原始问题的答案包含在 D[n] 中。

Python 代码：

F=['abcd','de','a','b','c','d']
S='abcde'

D = [ [] ]
for i in range(1,len(S)+1):
    s = S[:i]
    best = None
    for f in F:
        if s.endswith(f):
            a = D[i-len(f)]
            if a is None:
                continue
            if best is None or len(a) < len(best):
                best = a + [f]
    D.append(best)

print D[len(S)]

输出：

['a', 'b', 'c', 'de']

- Peter de Rivaz