[알고리즘]KMP

100만개의 사이트가 담긴 아스키 파일을 바탕으로 , NFqueue를 이용해서 HTTP 요청의 패킷이 해당 100개의 사이트 중 하나면 차단을 시켜야했다. 나는 그냥 Unordered_map ( 이하 , 해시맵 ) 을 사용해서 차단시킬라 했는데 익명의(?) 코딩천재 17살 고딩이 KMP + TRIE 알고리즘을 이용하면 훨씬 빠르다고 조언해줬다...

문자열 검색

일단 , 특정 배열안에서 내가 찾고자하는 문자열이 있는지 검사해보자.
좋은 예시로는 , 카카오톡의 대화방에서 문자검색 기능이나 혹은 크롬같은 브라우저에서 지원하는 문자열검색 기능이 존재할 것이다.

Normal한 방법

"이 세상에서 코카콜라가 제일 맛있어 , 펩시보다도 더 맛있는건 코카콜라야." 라는 words 문자열안에서 target "코카콜라"를 찾는다면 보통 사람들이 생각하는 CPP코드는 다음과 같을 것이다.

int main(int argc , char **argv){
	string words = "이 세상에서 코카콜라가 제일 맛있어 , \
    펩시보다도 더 맛있는건 코카콜라야.";
    sttring target = "코카콜라";
    vector<int> ans_idxs;
    for(int i=0;i<words.size();i++){
    	bool flag = false;
    	for(int j=0;j<target.size();j++){
        	if(words[i+j]!=target[j] || i+j>=words.size()) {
            	flag = true;
                break;
            }
        }
        if(!flag) ans_idxs.push_back(i);
    }
}

원본 문자열을 전부 순회하면서 , 각 순회마다 찾고자하는 target을 해당 지점에서 다시 순회한다. words의 길이가 N , target의 길이가 M이라고 할때 시간복잡도는 O(N*M)이 된다.

Can we do better?

위의 알고리즘은 , 검색을 하다가 하나만 틀릴경우 바로 포기해버리고 다음 인덱스로 넘어간다. 근데 사실 중요한 정보를 놓치고 있다.

• "ABCDABCDABEE" 에서 "ABCDABE" 패턴을 찾아보자

원래 대로라면 "ABCDAB" 까지는 일치하고 그 다음 인덱스가 "C"이므로 "E"가 나오지 않아서 틀렸다. 그럼, 다음 인덱스로 넘어가게 된다. 근데 다시 한번 유심히 생각해보자.
"ABCDABC" 까지 찾았는데 , 해당 문자열의 prefix 와 suffix가 "ABC"로 일치하는 것을 볼 수 있다. 즉, 다음 인덱스로 넘어갈 필요없이 suffix "ABC"의 시작인덱스 "A"로 넘어가서 검사를 시작하면 된다! 오오오 ....

구현

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;
}

구현인데, 사실 썩 마음에 와닿지는 않는다.
다음번에 , 직접 KMP 문자열 검색 관련 백준문제를 풀어보면서 구현해봐야겠다.