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

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

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

我正在寻找一个有效的数据结构/算法，将执行此比较。我能想到的，比如搜索内部通配符的所有有效的连击数的方法，例如

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

和使用任何的多字符串搜索算法（可能Aho–Corasick），但我不知道是否有更好的解。

来源

2012-06-01 Bryce

我附上了一个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)

来源

2012-06-01 18:13:40

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

回答

相关问题