자료구조 7장 - 문자열 검색

문자열 검색 이란 ?

 

 

어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함돼 있다면 어디에 위치하였는지 찾아내는 것

 

문자열에서 부분 문자열을 검색하는 방법은 브루트 포스법, KMP법, 보이어, 무어법 등이 있다.

 

브루트 포스법  O(N*M)  N-문자열  M-패턴

 

문자열 검색 방식에서 가장 기초적이고 단순한 알고리즘 

선형 검색을 단순하게 확장시킨 알고리즘

 

txt : 문자열

pat : 찾을 문자열 (패턴)

 

* (pt=pt-pp+1)  : txt배열에서 찾다가 패턴이 다르면 다음 인덱스로 돌아간다

ex) 3번째 부터 5번째까지 패턴이 같지만 6번째에 다르면 4번째 인덱스로 돌아감 

def bf_match(txt,pat):
      pt=0
      pp=0
 
      while pt != len(txt) and pp !=len(pat):
            if txt[pt] == pat[pp]:
                  pt+=1
                  pp+=1
            else:
                  pt=pt-pp+1
                  pp=0
                  
      if pp==len(pat):
            return pt-pp
      else:
            return -1
 

 

 

KMP법   O(N+M)  N-문자열 M-패턴 

 

브루트 포스법은 검사를 수행한 뒤 일치하지 않는 문자를 만나면 검사 결과를 버린다. 

하지만 KMP법은 이 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다.

 

 

 

def kmp_match(txt,pat):
      pt=1
      pp=0
      skip=[0]*(len(pat)+1)
 
      skip[pt]=0
      while pt!= len(pat):
            if pat[pt]==pat[pp]:
                  pp+=1
                  pt+=1
                  skip[pt]=pp
            elif pp==0:
                  pt+=1
                  skip[pt]=pp
            else:
                  pp=skip[pp]
 
      pt=pp=0
      while pt!=len(txt) and pp!=len(pat):
            if txt[pt]==pat[pp]:
                  pt+=1
                  pp+=1
            elif pp==0:
                  pt+=1
            else:
                  pp=skip[pp]
      return pt-pp if pp==len(pat) else -1