随机数英语单词

我会把字典里的单词 Trie 结构,然后从左到右读取字符串,并检查子字符串是否在trie中。如果他们有孩子,继续前进。如果它们恰好是一个叶子或一个有效的词,请添加到出现计数中。

在伪代码中:

Trie dict = ... // load dictionary
Dictionary occurences = {}

for i in length(string):
    j = i + 1
    # think of partial as string.Substring(i, j);
    while dict.hasChildren(partial):
        j++ 
        if isWord(partial):
            dict[partial]++

这样你就可以保证它不会错过任何一场比赛,同时还要寻找一切可能。

您可以通过更改 j 初始化为或通过拒绝 isWord() 方法(SO) a 不是一个“有效”的词)。

这个 Aho-Corasick string matching algorithm 在字典大小的时间线性中构建匹配结构,并在输入文本大小的时间线性中匹配模式+找到的匹配数。