1

要素が必ずしも隣接している必要はありませんが、N 文字以内で発生する必要がある部分列を文字列で検索しているとします。そう、

search("abc","aaabbbccc",7) => True
search("abc","aabbcc",3) => False

この比較を実行する効率的なデータ構造/アルゴリズムを探しています。内部ワイルドカードのすべての有効な組み合わせを検索するなど、いくつかのアプローチを考えることができます。

search("abc",whatever,4) => "abc","a*bc","ab*c"

複数文字列検索アルゴリズム (おそらくAho–Corasick ) のいずれかを使用していますが、より良い解決策があるかどうか疑問に思っています。

4

1 に答える 1

1

あなたが望むことを行うpythonコードサンプルを添付しました。検索する文字列をループし、検索文字列の最初の文字が見つかった場合、長さ = max_length の部分文字列が作成され、別の関数に送信されます。この関数は、検索文字列のすべての文字を順番に見つけようとして、部分文字列を単純に移動します。すべて見つかった場合は True を返し、そうでない場合は False を返します。

def check_substring(find_me, substr):
    find_index = 0
    for letter in substr:
        if find_me[find_index] == letter:
            find_index +=1
        # if we reach the end of find_me, return true
        if find_index >= len(find_me):
            return True
    return False

def check_string(find_me, look_here, max_len):
    for index in range(len(look_here)):
        if find_me[0] == look_here[index]:
            if check_substring(find_me, look_here[index:index + max_len]):
                return True
    return False



fm = "abc"
lh = "aabbbccceee"
ml = 5

print check_string(fm, lh, ml)
于 2012-06-01T18:13:40.787 に答える