在字符串中查找不相邻的子序列

Question

>假设我正在一个字符串中搜索一个子序列，其中元素不一定是相邻的，但必须在 N 个字符内出现。所以

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

我正在寻找一种有效的数据结构/算法来执行此比较。 我可以想到一些方法，例如搜索内部通配符的所有有效组合，例如

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

并使用任何多字符串搜索算法（可能是 Aho-Corasick），但我想知道是否有更好的解决方案。

Answer 1

我附上了一个python代码示例，可以做你想要的。它循环访问要搜索的字符串，如果找到搜索字符串的第一个字母，则创建 length=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)