如何从字符串中对所有可能的单词进行排序？

Question

我想知道如何继续这项任务,拿这个字符串例如"thingsandstuff".

我怎么能从这个字符串中生成所有可能的字符串,以便根据英语字典单独查找它们？

目标是在不包含空格的字符串中查找有效的英语单词.

谢谢

Answer 1

另一种可能性是反过来,而不是从字符串生成子串,抓取所有候选词并将它们与字符串匹配.

您可以存储原始字符串中单词的索引对(开始,结束).

这可以在正则表达式可以轻松完成,或者,如果没有足够的高性能,以str.find(),或者甚至没有足够的高性能与更复杂的字典索引方案或妙语什么可以和无法比拟的(见格雷格的答案的想法)

在这里你有一个我的意思的样本

candidate = "thingsandstuffmydarlingpretty"
words = file('/usr/share/dict/words').read()
#This generator calls find twice, it should be rewritten as a normal loop
generate_matches = ((candidate.find(word),word) for word in words.split('\n')
                     if candidate.find(word) != -1 and word != '')

for match in generate_matches:
    print "Found %s at (%d,%d)" % (match[1],match[0],match[0] + len(match[1]))

Answer 2

人们谈论这个,好像问题的顺序是可能的子串的数量.这是不正确的.这个问题的正确顺序是:

O(min(字母数字,子字符串数组合)*comparison_cost)

因此,在Vinko上构建问题的另一种方法是将字典索引 (例如,对于字典中的每个作品,确定该单词中的字母,单词的长度等).这可以大大加快速度.作为一个例子,我们知道目标"女王"不能匹配"斑马"(没有z!)(或任何包含z,r,b,a ......的单词)等.此外,将dict中的每个单词存储为排序字符串('zebra' - >'aberz')并执行"string in string"(最长公共子字符串)匹配.'eenuq'vs'abarz'(不匹配).

(注意:我假设原始单词中的字母顺序无关紧要 - 它是一个'字母包',如果有,则相应调整)

如果你有很多单词可以同时比较,可以使用像KMP这样的东西进一步降低比较成本.

(另外,我直接进去,做了一些亚历克斯没有的假设,所以如果他们错了,那就闭口!)