有没有更好的方法来查找出现在给定字典中的字符串的所有相邻子字符串

Question

是否有比以下算法更有效的算法来查找给定语言的所有子字符串：

import string.ascii_lowercase as alphabet
languge = {'aa', 'bc', 'wxyz', 'uz'};
for i in xrange(len(alphabet)):
    for j in xrange(i,len(alphabet)):
        substirng = alphabet[i:j+1]
        if substirng in languge:
            print substirng

Answer 1

为此，请使用Aho-Corasick或Rabin-Karp算法：

It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously

这些算法有许多Python实现。在

Aho-Corasick搜索的复杂性是O(TextLength + AnswerLength)，预处理O（n*σ），其中n是字典中所有单词的总长度，σ是字母表大小

Rabin-Karp的平均时间也是O(TextLength + AnswerLength)，但最差的时间是{}

Answer 2

如果你用 from string import ascii_lowercase as alphabet

language = {'aa', 'bc', 'wxyz', 'uz'}

for item in language:
    if item in alphabet:
        print item

这是可行的，但列表理解是首选的

^{pr2}$

Answer 3

如果我没弄错你的问题。你有字母表或字符串。在本例中是一个由26个字符组成的字符串，a-z。您希望检查给您的任何字符串是否是上述“字母表字符串”的子字符串。在

如果真是这样，还有更好的办法。在

您当前的方法相当于从字母表中计算所有可能的子字符串，对于大小为N的字母表，它是O（N^2），在您的特定情况下是26^2，然后检查子字符串是否属于预定义的集合。更好的方法是简单地循环给定的字符串和check if they are substrings of your alphabet。这是一个O（N）操作，用于预定义集中的每个字符串。这将复杂性降低到O（NM）。在

如果M明显小于N，这就更好了

也许还有更好的方法，但这是一个好的开始。在