[ 알고리즘 ] 25. String matching 2 - KMP

지금껏 비효율적인 String matching이 많았다.

 

 

이렇게  ababac의 패턴과 ababaa를 비교하는 중에 Mismatching이 발생하면

다시 한 칸만 가서 비교하는 것이 아니라 ab단위로 움직여도 되지 않겠나 생각할 수 있다.

 

한 칸만 움직여서 다시 비교하는 게 아니라 몇 칸 더 가서 다시 비교를 시작해도 된다는 것이다.

 

여기에서 abaa와 abab를 비교할 때 마지막에서 또 Mismatch가 발생한다.

그럼 p를 한 칸만 옮겨서 비교하면 바로 MisMatch인 게 눈에 훤하다.

다시 a랑 비교를 시작해줘야 하기 때문에 아래와 같이 이동해야한다.

 

 

 

※ 참고할 점

Shift를 할 수 있는 숫자의 후보 중에서

가장 조금만 Shift를 한다.

 

s' + k = s + q 이다.

둘 다 빨간 동그라미 a를 지칭한다.

패턴끼리만 비교해도

#번째 Index에서 mismatching이 생기면 몇 번째 인덱스부터 다시 하겠다. 할 수 있음

ABABAC이면

 

앞에 AB 중에 Mismatching이면 다시 처음부터 시작

두 번째 AB 중에서 Mismatcing이 생기면 그 앞에 있었던 A혹은 B부터 다시 시작...

 

 

---

 

Prefix 계산

 

 

 

패턴끼리 서로 비교할 때는 0번과 0번으로 같이 비교를 시작하면 무조건 같으니까 

시작할 때 둘 중 하나는 인덱스를 +1시켜서 한다.

 

막대기에 닿을 때까지 같아야 하는 String을 찾는다.

 

나머지는 구해보기 ▼

 

 

 

---

Example 

 

이렇게 주어져 있을 때 비교를 해보자.

 

처음 AB를 한 뒤에는 C에서 Mismatching이 생긴다.

뭐 딱히 반복된 패턴이 나온 게 없으므로 match가 되었던 B까지는 통과 시키고

C로가서 다시 비교를 시작한다.

 

바로 mismatching

저렇게 까지 간다.

 

ABABAB까지는 맞고 마지막 AB랑 CB가 안 맞으니 Mismatching.

6개까지 맞으므로 ㅠ(6)=4 이다.

이는

7번째에서  Mismatch이면 P[3]까지는 다시 비교할 필요없음 이란 뜻이므로,

그 다음 번엔 현재 Mismatcing이 발생한 위치에서부터 다시 P[4]부터 가져다가 비교를 한다.

내가 질문한 거 ▼

 

결과▼

 

 

 

---

Case별로 나눠보기

 

 

 

P[1]과 T[i]와 같지 않을 때, i ++ 

사실 T가 움직이는 거임

 

 

 

P의 첫 번째 말고 다른 값과 T와 일치하지 않았을 경우

 

P를 ㅠ값만큼 옮긴다.

 

.

 

 

 

Psuedo Code

 

 

q를 증가시키고 비교하는 게 아니라, 

P[q+1]을 보고 어떤가 하고, 상황에 맞게 증가시킨다.

 

for 안에서 처음 있는 while : Case 2

 

for && 첫 if랑 mismatching = Case 1

for  && 첫 if에 대 해당 = Case 3

 

 

풀어보라고 하셨긴 함

 

(출처)

한동대학교 용환기교수님 - 알고리즘