길이가 k 인 일반적인 부분 문자열

Question

2 개의 문자열과 정수 'k'를 얻고 길이가 모두 2 인 문자열의 공통 부분 문자열을 반환하는 함수를 작성하려고합니다. (1보다 크면 임의로 하나를 반환합니다). 가장 일반적인 공통 부분 문자열을 확인하는 알고리즘이 많이 있지만, k- 길이 부분 문자열을 검사하는 알고리즘이 없습니다.

내가 최적화하기를 원한다면 해시 테이블을 사용하는 것이 올바른 방법이라고 생각하지만 꽤 이해할 수는 없습니다.

목록에 k-length 이상의 시퀀스가 ​​있는지 확인하는 함수 만 작성할 수 있습니다. 여기 은 내가 가진 것입니다 :

def repeat(st, k): 
    for i in range(len(st) - k + 1): 
     for j in range(i + 1, len(st) - k + 1): 
      if st[i : i + k] == st[j : j + k]: 
       return st[i : i + k] 
    return False 

내가이 어떤 도움을 주셔서 감사합니다 것입니다 ... :

def substrings_of(s, k): 
    for i in xrange(0, len(s) - k): 
     yield s[i:i+k] 

def common_substr(a, b, k): 
    for a_s in substrings_of(a, k): 
     for b_s in substrings_of(b, k): 
      if a_s == b_s: 
       return a_s 

Answer 1

간단한 버전 :/

Answer 2

이 더 효율적인 또는 영리 솔루션는 아니다 바로 이것입니다 :

def common_substr(a, b, k): 
    for substr in (a[i:i+k] for i in range(len(a)-k+1)): 
    if substr in b: 
     return substr 

나는 매우 큰 입력 문자열 s (예 : 지. 텍스트)와 큰 k의 메가 바이트이 너무 비효율적이고 속도를 향상시킬 수있는 길이 k의 가능한 모든 문자열의 해시를 구축 할 수 있습니다

def common_substr(a, b, k): 
    substrs = set(a[i:i+k] for i in range(len(a)-k+1)) 
    for substr in (b[i:i+k] for i in range(len(b)-k+1)): 
    if substr in substrs: 
     return substr 

을하지만 주변이 훨씬 영리 알고리즘이 있다고 생각한다. 비교적 단순한 strstr() (문자열의 문자열 찾기)조차 모두가 구현할 수있는 단순한 것보다 효율적인 솔루션을 제공합니다.