robustflame의 블로그

Knuth-Morris-Pratt Pattern Searching 긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다. 구현#include using namespace std; // 문자열 A에서 문자열 B와 일치하는 위치를 모두 찾는다. vector KMPSearch(const string& A, const string& B) { int AN = A.length(), BN = B.length(); // 부분 일치 테이블 생성 vector pi(BN, 0); int matched = 0; for (int i = 1; i 0 && B[i] !..