패턴찾기 알고리즘

우리는 일상생활에서 cntl+f 같은 문자열속에서 특정 패턴을 찾아내는 행위를 자주 사용하고 있다.
이때 우리가 생각하는 것처럼 처음부터 읽고 비교하는 방식으로(Navie Algorithm)으로 가면 성능이 매우 안좋을 것으로 예상된다. 그렇다면 어떤 알고리즘을 사용해야 효율적으로 패턴을 찾을 수 있을까?

KMP Algorithm

KMP Algorithm은 Knuth, Morris, Prett가 고안하였다고하여 그 앞글자를 따 이름 지어졌다.
이 알고리즘은 검사 대상 문자열의 길이를 N, 패턴의 길이를 M이라고 하였을 때
시간 복잡도가 O(N+M)으로 매우 효율적이다. (Navie는 O(NM))

어떤 원리로 동작하는 걸까?

접두사(Prefix)와 접미사(Suffix)

KMP 알고리즘을 이해하기 위해서는 접두사와 접미사의 개념을 먼저 이해해야한다.
우리가 영어/국어 시간에 배운 개념을 이용하여 직관적으로 이해할 수있다.

(예시)
<abcabcd의 접두사>
a
ab
abc
abca
abcab
abcabc
abcabcd

<abcabcd의 접미사>
d
cd
bcd
abcd
cabcd
bcabcd
abcabcd

여기서 접두사와 접미사의 겹치는 부분이 보이지 않는가?
KMP 알고리즘에서는 이 겹치는 문자열의 길이를 이용한다.
예를 들어 ( i = 접두사와 접미사가 겹치는지 검사할 길이 ) 라고 정의할때,
i일때 겹치는 길이를 저장하는 배열 pi[i]는 다음과 같을 것이다.

i	부분문자열	pi[i]
0	a	0
1	ab	0
2	abc	0
3	abca	1
4	abcab	2
5	abcabc	3
6	abcabcd	0

코드

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> getPi(string p){
	int m = (int)p.size(), j=0;
	vector<int> pi(m, 0);
		for(int i = 1; i< m ; i++){
            while(j > 0 && p[i] !=  p[j])
				j = pi[j-1];
               	if(p[i] == p[j])
     			  pi[i] = ++j;
      		}
     		
			return pi;
        }
      
        
 vector<int> kmp(string s, string p){
            vector<int> ans;
            auto pi = getPi(p);
            int n = (int)s.size(), m = (int)p.size(), j =0;
            for(int i = 0 ; i < n ; i++){
                while(j>0 && s[i] != p[j])
                    j = pi[j-1];
                if(s[i] == p[j]){
                    if(j==m-1){
                        ans.push_back(i-m+1);
                        j = pi[j];
                    }else{
                        j++;
                    }
                }
            }        
            return ans;
        }
      
      
int main(){
	string s, p;
	getline(cin, s);
	getline(cin, p);
	auto matched = kmp(s,p);
	printf("%d\n", (int)matched.size());
	for(auto i : matched)
		printf("%d ", i+1);

	return 0;
        }