기본 문자열 일치 알고리즘

Question

다음은 고유 문자열 일치에 대한 매우 유명한 질문입니다. 누군가 제게 해답을 설명해 주실 수 있습니까?

패턴 P의 모든 문자가 서로 다르다고 가정합니다. 는 n 문자 텍스트 T.에 시간 O (N)에서 실행 순진-STRING의 정규 표현을 촉진하는 방법을 보여

Answer 1

기본 개념 :

• 입력을 반복 처리와 동시에 패턴 패턴 문자가 모두 있기 때문에이 작동

한, 당신은 둘 사이에 일치하지 않는 문자를받을 때마다 서로

자신의 캐릭터를 비교, 당신은 단지 패턴의 위치를 ​​재설정하고 입력 위치를 유지할 수 있습니다 다른 의미는 부분 일치가있을 때마다 그 부분과 겹치지 않는 부분이있을 수 있으므로 부분 일치가 끝날 때부터 살펴볼 수 있습니다. ,

input[n] 
pattern[k] 
pPos = 0 
iPos = 0 
while iPos < n 
    if pPos == k 
    FOUND! 
    if pattern[pPos] == input[iPos] 
    pPos++ 
    iPos++ 
    else 
    // if pPos is already 0, we need to increase iPos, 
    // otherwise we just keep comparing the same characters 
    if pPos == 0 
     iPos++ 
    pPos = 0 

그것은 적어도 iPos 증가마다 두 번째 루프, 따라서 대부분의 2n 루프가 실행에있을 수 있다는 것을 쉽게 알 수 제작 : 여기

은 이해하기 너무 어려운 안되는 의사 코드이다 실행 시간은 O(n)입니다.

Answer 2

NAIVE-STRING-MATCHER에서 T [i]와 P [j]가 일치하지 않으면 T [i] 이전의 모든 문자를 건너 뛰고 T [i + 1]에서 P [1]로 새로운 일치를 시작할 수 있습니다.

나이브 문자열 정합 기의 0

3 내지 N (T, P)

1 N 길이 [T]

2m 길이 [P] - m

4라면 P [1. . m] = T [s + 1. . S의 +의 m]

5 다음 파이썬 2.7에서의 "패턴이 변화 발생"

Answer 3

나이브 문자열 검색 알고리즘 구현을 인쇄 : 보이어 - 무어의 문자열 검색 알고리즘을 구현하는 중간에 https://gist.github.com/heyhuyen/4341692

, 내가 내 원래의 순진 검색 알고리즘으로 게임하기로 결정했습니다. 그것은 검색 할 문자열을 취하는 인스턴스 메소드로 구현됩니다. 객체에는 'pattern'속성이 있습니다.이 속성은 일치시킬 패턴입니다.

1) 이중 for 루프를 사용하는 검색 방법의 원래 버전입니다. 여기 번째 버전이다 대신 이중 동안 루프를 사용하여 통화를 다양하게하고 LEN

def search(self, string): 
    for i in range(len(string)): 
     for j in range(len(self.pattern)): 
      if string[i+j] != self.pattern[j]: 
       break 
      elif j == len(self.pattern) - 1: 
       return i 
    return -1 

2). 약간 빠른 제작하지 호출

def search(self, string): 
    i = 0 
    while i < len(string): 
     j = 0 
     while j < len(self.pattern) and self.pattern[j] == string[i+j]: 
      j += 1 
     if j == len(self.pattern): 
      return i 
     i += 1 
    return -1 

3) 여기서 xrange 원래, 교체 범위 범위. 앞의 두 개보다 빠릅니다.

def search(self, string): 
    for i in xrange(len(string)): 
     for j in xrange(len(self.pattern)): 
      if string[i+j] != self.pattern[j]: 
       break 
      elif j == len(self.pattern) - 1: 
       return i 
    return -1 

4) 로컬 변수에 값 저장 = win! 이중 while 루프에서는이 속도가 가장 빠릅니다.

def search(self, string): 
    len_pat = len(self.pattern) 
    len_str = len(string) 
    i = 0 
    while i < len_str: 
     j = 0 
     while j < len_pat and self.pattern[j] == string[i+j]: 
      j += 1 
     if j == len_pat: 
      return i 
     i += 1 
    return -1