알고리즘 ch11 String match

String

- 문자의 나열

- Substring : 연속되는 부분 문자열, Subsequence : 연속되지않는 부분 문자열

예시로 ACDEF와 ABKEF가 있다고 하자.

substring = EF

     ACDEF

     ABKEF

subsequence = AEF

    ACDEF

    ABKEF

- Prefix : 문자열의 첫번째 문자부터 시작되는 부분문자열, Suffix : 문자열의 마지막문자부터 거꾸로 보는 부분문자열

예시로 문자열 ALGORITHM이 있다고 하자

prefix = A

AL

ALG

ALGO

.

.

.

ALGORITHM

suffix  = M

HM

THM

ITHM

.

.

.

ALGORITHM

본인 자기자신의 문자열을 제외하면 proper prefix, proper suffix라고 한다.

예시로 설명하자면 ALGORITHM 을 제외한 것

String match problem

- string T(text)와 P(pattern)을 주고, T의 substring 중에 P를 찾는 문제

- 해결알고리즘

 1) Brute-force algorithm : Naive algorithm 이라고도 한다.

 pattern을 찾을 때까지 문자열의 처음부터 끝까지 확인하는 방법

 (n이 문자열의 길이, m이 찾으려는 패턴의 길이일때)

 O(nm)의 시간복잡도를 가진다.

 2) Knuth-Morris-Pratt's algorithm : 줄여서 KMP algorithm

 패턴의 왼쪽부터 오른쪽으로 비교한다.

 비교할 필요가 없는 부분은 뛰어넘음으로서 비교속도가 빨라진 방법이다.

    뛰어넘을 위치는 패턴의 접두사와 접미사(둘다 proper)를 이용해 미리 배열을 만들어 놓는다. 

j를 지금 비교하고 있는 패턴의 인덱스라고 할 때

F[i] = 패턴 P의 인덱스 0~j까지의 부분 문자열에서 접두사 == 접미사일 수 있는 최대 길이

(단, 접두사와 접미사는 부분 문자열과 같아선 안 되며 접두사와 접미사는 겹치는 부분이 있어선 안 된다.)

배열을 만드는 algorithm failureFunction(P) 의 수도코드

F가 뛰어넘을 위치를 저장하려는 배열일때

 failureFuction()의 시간복잡도 O(m)

F배열을 이용해 KMP 구현

failureFucntion()과 거의 일치, 

Text와 Patternt이 mismatch시 failureFunction()으로 구한 배열을 이용한다는 점.

Text의 인덱스 i는 최대로 1번씩 증가하여 O(n)

따라서 KMP의 시간복잡도는 O(m+n)

KMP algorithm은 optimal algorithm이기도 하다.

 3) Boyer-Moors algorithm : 2가지의 heuristic을 기반으로 진행

* Looking glass heuristic : 패턴의 오른쪽에서 왼쪽으로 비교한다.

* Character-jump heuristic : mismatch 발생시 KMP 처럼 비교할 필요가 없는 부분은 뛰어넘는다.

   비교는 오른쪽에서 왼쪽이지만 이동은 왼쪽에서 오른쪽임을 주의

뛰어넘을 위치 배열 만드는 lastOccurenceFunction()함수

Text에 들어있는 문자들의 집합 배열에 패턴 내에 각자 문자가 마지막으로 나오는 인덱스 저장

예를 들어 

패턴 P = abacab , ∑ = {a,b,c,d} 일 경우.

처음에 배열을 -1로 초기화하고 각자 인덱스 저장

σ	a	b	c	d
L(σ)	4	5	3	-1

-> d처럼 pattern에 들어있는 않는 character을 bad character

    

∑ : string을 구성하는 character들의 집합

lastOccurenceFunction()의 시간복잡도 : O(s+m), s는 ∑의 크기 m은 pattern의 크기

뛰어넘을 배열을 사용한 BM algorithm의 수도코드

예시문제

Boyer-Moore algorithm의 최악의 경우 예시

최악의 경우 시간복잡도는 O(nm + s)

KMP랑 BM을 비교하자면, 평균적인 경우는 BM이 빠르나 위와 같은 최악의 경우는 BM이 훨씬 느리다.