문자열에서 인접하지 않은 하위 시퀀스를 찾습니다.

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

원하는 것을 수행하는 파이썬 코드 샘플을 첨부했습니다. 검색 할 문자열을 반복하며 검색 문자열의 첫 번째 문자가 발견되면 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)