KMP ALPS 알고리즘 세미나 2017. 10. 27. 김태리

Pattern Matching Problem Given strings text T and patten P, find a position of a substring of T equal to P. text T a b c d pattern P a b c **string : a sequence of characters JTKIM

Brute-Force Pattern Matching left-to-right T의 제일 앞에서 시작, 각 shift에 대하여 모두 비교 시행 i=0 a b c d i+j j : 0 to m-1 a b c JTKIM

Brute-Force Pattern Matching left-to-right T의 제일 앞에서 시작, 각 shift에 대하여 모두 비교 시행 i=1 a b c d i+j j : 0 to m-1 a b c JTKIM

Brute-Force Pattern Matching left-to-right T의 제일 앞에서 시작, 각 shift에 대하여 모두 비교 시행 i=2 a b c d i+j j : 0 to m-1 a b c JTKIM

Brute-Force Pattern Matching left-to-right T의 제일 앞에서 시작, 각 shift에 대하여 모두 비교 시행 i=n-m a b c d i+j j : 0 to m-1 a b c JTKIM

Brute-Force Pattern Matching left-to-right T의 제일 앞에서 시작, 각 shift에 대하여 모두 비교 시행 1 2 3 4 5 6 7 8 9 10 11 12 n <- size of text T m <- size of pattern P   for i <- 0 to n-m     j <- 0     while j < m and T[i+j] = P[j]         j <- j+1     if j = m         return i    // match at i     else          break while loop    // mismatch return -1    // no match anywhere O(nm) n: size of T, m: size of P worst case? T = aaa…ah P = aaah JTKIM

KMP (Knuth-Morris-Pratt) 앞과 같이 left-to-right 보완: shift를 더 intelligently! DP mismatch 발생 시- 이동가능한 최대로 이동하여 불필요한 comparison을 줄인다 largest prefix of P[0,j] that is a suffix of P[1,j] 찾는 것: 실패함수 Failure Function String Matching a b c a b j a b F(j-1) JTKIM

Failure Function String Matching KMP (Knuth-Morris-Pratt) Failure Function String Matching JTKIM

1. Failure Function 실패함수 pattern P에 대해 전처리를 실시 j=0 은 0, j=1부터 진행 F(j) :the size of the largest prefix of P[0,j] that is also a suffix of P[1,j] j 1 2 3 4 5 P[j] a b c F(j) JTKIM

1. Failure Function 실패함수 j 1 2 3 4 5 P[j] a b c F(j) 1 1 2 6 7 8 9 10 11 12 13 14 15 16 17 /*FailureFunction(P)*/ m <- size of pattern P F[0] <- 0 i <- 1 j <- 0   while i < m     if P[i] = P[j]   //matched j+1 characters         F[i] <- j+1         i <- i+1         j <- j+1     else if j>0 then  //use failureFunction to shift P         j <- F[j-1]     else             //no match         F[i] <- 0         i <- i+1      j 1 2 3 4 5 P[j] a b c F(j) 1 1 2 Time Complexity: O(m) 각 while loop i 는 1씩 증가 또는 shift amount i-j 최소 1씩 증가(F(j-1)<j) JTKIM

mismatch (P[j] != T[i]) 발생 시 2. String Matching a b c a b 1 a 2 c 3 a 4 b a b c mismatch (P[j] != T[i]) 발생 시 j  F(j-1) j 1 2 3 4 5 P[j] a b c F(j) JTKIM

mismatch (P[j] != T[i]) 발생 시 2. String Matching a b c 1 2 3 4 b a b c a b c mismatch (P[j] != T[i]) 발생 시 j  F(j-1) j 1 2 3 4 5 P[j] a b c F(j) JTKIM

mismatch (P[j] != T[i]) 발생 시 2. String Matching a b c 1 2 3 4 a b 1 a 2 c 3 a a b c a b c a b c mismatch (P[j] != T[i]) 발생 시 j  F(j-1) j 1 2 3 4 5 P[j] a b c F(j) JTKIM

mismatch (P[j] != T[i]) 발생 시 2. String Matching a b c 1 2 3 4 a a b c a b c a b c a b c mismatch (P[j] != T[i]) 발생 시 j  F(j-1) j 1 2 3 4 5 P[j] a b c F(j) JTKIM

2. String Matching a b c 1 2 3 4 a b 1 a 2 c 3 a 4 b 5 a b c a b c a b 1 2 3 4 a b 1 a 2 c 3 a 4 b 5 a b c a b c a b c a b c a b c j 1 2 3 4 5 P[j] a b c F(j) JTKIM

2. String Matching a b c 1 2 3 4 a 4 b 5 a 2 c a b c a b c j 1 2 3 4 5 1 2 3 4 a 4 b 5 a 2 c a b c a b c j 1 2 3 4 5 P[j] a b c F(j) JTKIM

2. String Matching failure func과 유사 각 while loop i 는 1씩 증가 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /*KMP(T,P)*/ F<-failureFunction(P) i<-0 j<-0 while i<n     if T[i] = P[j]         if j=m-1             return i-j //match pos         else              i<-i+1             j<-j+1     else         if j>0             j<-F[j-1]         else   return -1    //no match failure func과 유사 각 while loop i 는 1씩 증가 또는, i-j (shift amount) 최소 1씩 증가  O(n) 따라서, O(n+m) JTKIM

BOJ 1786 ‘찾기’ https://www.acmicpc.net/problem/1786 BOJ 5525 ‘IOIOI’ https://www.acmicpc.net/problem/5525 KMP 문제모음 https://www.acmicpc.net/problem/tag/KMP JTKIM

http://blog.myungwoo.kr/101 http://bowbowbow.tistory.com/6 JTKIM