string - 使用动态编程查找字符串中最长的单词？

Question

当我看到一个问题询问我是否可以从字符串中找到最长的单词（字符串没有空格，只有字符）时，我已经开始研究一些算法问题。经过一段时间的思考，我只是想确认我是否可以使用动态编程来解决类似于最大连续和问题的问题。在解析每个字符之后，我可以调用 isWord 方法（已经实现），然后如果它继续转到下一个字符并增加单词长度，如果不是，那么只需将计数器重置为零并开始从该索引中查找一个单词. 请让我知道这是否是一个好方法，否则请指导我有什么更好的方法来解决这个问题。

谢谢你们的帮助。

-维克

Answer 1

该算法将无法正常工作。考虑以下字符串：

BENDOCRINE

如果您从字符串的开头开始并在您还有一个单词时向前扫描，您会找到单词“BEND”，然后在该点之后重置字符串并从 O 开始。这里的正确答案是选择“内分泌”这个词要长得多。

如果您有一个静态字典，并且想从该字典中找到包含在文本字符串中的最长单词，您可能需要查看Aho-Corasick 算法，它将在文本字符串中找到一组字符串的每一个匹配项，并且这样做非常有效。您可以轻松修改算法，以便它随时跟踪它输出的最长单词，这样它就不会输出比目前找到的最长单词更短的字符串，在这种情况下，运行时间将为 O(n + m)，其中n 是要搜索的文本字符串的长度，m 是所有合法英语单词中的字符总数。此外，如果您提前进行 O(m) 预处理，那么从那时起，您可以在 O(n) 时间内找到给定字符串中最长的单词，其中 n 是字符串中的字符数。

（至于为什么它运行时间为 O(n + m)：通常运行时间是 O(n + m + z)，其中 z 是匹配的数量。如果你限制输出的匹配数量，那么你永远不会输出一个比目前最长的单词短，最多可以输出n个单词，因此运行时间为O(n + m + n) = O(n + m))。

希望这可以帮助！

Answer 2

动态编程不适用于您的问题：

让 seq1 和 seq2 为 2 个字符序列

isWord(Concatenation(seq1, seq2)) 不能从 isWord(seq1) 和 isWord(seq2) 的值推断出来