KMP Pattern Searching

Knuth-Morris-Pratt Pattern Searching

---

긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다.

구현

#include <bits/stdc++.h> using namespace std; // 문자열 A에서 문자열 B와 일치하는 위치를 모두 찾는다. vector<int> KMPSearch(const string& A, const string& B) { int AN = A.length(), BN = B.length(); // 부분 일치 테이블 생성 vector<int> pi(BN, 0); int matched = 0; for (int i = 1; i < BN; i++) { while (matched > 0 && B[i] != B[matched]) matched = pi[matched - 1]; if (B[i] == B[matched]) ++matched; pi[i] = matched; } // 패턴 검색 vector<int> ret; matched = 0; for (int i = 0; i < AN; i++) { while (matched > 0 && A[i] != B[matched]) matched = pi[matched - 1]; if (A[i] == B[matched]) ++matched; if (matched == BN) ret.push_back(i - matched + 1); } return ret; } int main() { string text = "abababaaaababaaabaabaabaaabaababaababaaabbaa"; string pattern = "ababa"; vector<int> ans = KMPSearch(text, pattern); for (int i = 0; i < ans.size(); i++) { printf("%d ", ans[i]); } printf("\n"); }

예제

• BOJ 10266 시계 사진들