[Python]문자열 알고리즘1 백준 1786

   문제

   https://www.acmicpc.net/problem/1786

컴퓨터를 사용하는데 있어 필수적인 기능이라고 볼 수 있겟다.

웹검색은 물론 파일을 찾거나 문서의 내용을 살펴볼때 등 많은곳에서 이용된다.

문자열을 검색하는데 가장 기본적을 생각해볼수 있는 방법은 한문자씩 이동해가며 

문자열을 찾는것이다.

abdabc 에서 abc를 찾기위해서는

abdabc 

abc

abdabc

   abc

abdabc

      abc

abdabc

        abc

이런식으로 한칸씩 이동하며 비교하는 방법이다.

하지만 이방법은 너무 오래걸린다. O(nm)이다.

KMP알고리즘을 이용해보자.

https://ko.wikipedia.org/wiki/%EC%BB%A4%EB%88%84%EC%8A%A4-%EB%AA%A8%EB%A6%AC%EC%8A%A4-%ED%94%84%EB%9E%AB_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

KMP알고리즘은 문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수를 

이용하여 O(n+m)으로 만들어준다.

실패함수를 만드는데 O(m)실패함수를 통해 문자열을 검색하는데 O(n)의 시간복잡도를

 가진다.

실패함수는 KMP알고리즘 실행중, 일치하지 않는 문자가 있을때 어디서부터 검색을 해야

할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재이다.

패턴의 처음부분부터 해당위치까지 즉 접두사와 접미사가 몇개나 일치하는지 기록하는

 부분 일치 테이블(partial match table or fail function)을 만드는 것이라고 보면된다.

예를 통해 살펴보자.

ABABC라는 패턴 P가 있을때 위치를 나타내는 변수 i,j를 통해 비교해보자

i는 1씩 증가하며 패턴의 위치를 가르킨다.

j는 접미사의 위치를 가르키게된다.

ABABC

i=1

ABABC

j=0

P[i]와 P[j]는 같지않다. 

p_table[1]=0으로 기록한고 i만 증가시킨다.

ABABC

i=2

ABABC

j=0

P[i]와 P[j]가 같다

 p_table[2]에 j+1인 1을 기록하고 i와 j를 증가시킨다.

ABABC

i=3

ABABC

j=1

P[i]와 P[j]가 이번에도 같다.

p_table[3]에 j+1을 기록하고 i와 j를 증가시킨다.

ABABC

i=4

ABABC

j=2

P[i]와 P[j]는 같지않다. 

이때는 j=table[j-1]로 되돌리고 다시 비교해준다. j를 0으로 되돌리지 않는다!

이부분이 예제에서는 잘 이해되지 않을수도 있지만

AACAAA라는 예제를 생각해보면 알수있다.

010122라는 부분 일치 테이블이 나온다는것을 알고 생각해보자.

이렇게 만들어진 부분 일치 테이블을 이용하면 이제 O(n)의 시간으로 문자열을 검색

할수있다.

ABABABCABABC

ABABC

부분 일치 테이블을 만들때와 방법은 비슷하다.

문자열과 패턴의 문자를 하나씩 비교해가며 일치하지 않을경우 만들어놓은 부분 일치 

테이블을 통해 패턴을 가르키는 위치를 지정할수있다.

과정은 생략하고 설명만 하겠다.

문자열의 가르키는 위치 i 패턴의 위치를 가르키는 j를 이용한다.

i는 1씩증가하며 j는 일치할경우 증가시키고 일치하지않을경우 j=table[j-1]로 위치를 

바꾸어 다시 비교한다.

j가 패턴의 끝에서 즉 len(P)-1과 같을때 T[i]와 일치한다면 문자열에서 패턴을 찾은

경우이다.

코드를 통해 살펴보면 이해하기 쉬울 수 있다.

import sys
 
T=sys.stdin.readline().replace("\n","")#문자열
P=sys.stdin.readline().replace("\n","")#패턴
 
KMPTable=[0 for _ in range(len(P))]
def MakeTable(P,KMPTable):
    j=0
    for i in range(1,len(P)):
        while j>0 and P[i]!=P[j]:#같지않을때
            j=KMPTable[j-1]#이전의 맞은부분곳까지 돌아가서 다시비교
        if P[i]==P[j]:#같을시
            j+=1#j를 증가시키고
            KMPTable[i]=j#테이블 갱신
 
def KMP(T,P,KMPTable):
    MakeTable(P, KMPTable)
    j=0
    count=0
    result=[]
    P_size=len(P)
    for i in range(len(T)):
        while j>0 and T[i]!=P[j]:#같지않을때
            j=KMPTable[j-1]#이전의 맞은부분곳까지 돌아가서 다시비교
        if T[i]==P[j]:#같으면
            if j==P_size-1:
                count+=1#개수 추가
                result.append(i-P_size+2)#위치추가
                j=KMPTable[j]#위치를 옮겨주고 다시탐색
            else:#j를 늘려준다
                j+=1
    return count,result
 

파이썬에서는 문자를 받을때 있어 그냥 sys.stdin.readline() 사용한다면 마지막에

개행문자(\n)가 붙게된다. 이부분을 제거해주자.