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 回答