문자열 검색 알고리즘 (KMP)

일반적으로 문자열에서 패턴을 검색한다고 할 때, 모든 경우를 검색해야 할 것이다.

KMP (Knuth Morris Pratt) 알고리즘

모든 부분을 비교하지 않아도 부분 문자열을 찾을 수 있는 알고리즘

1. 접두사와 접미사가 일치하는 최대 길이 찾기
2. 일치하는 경우에는 점프할 수 있다

알고리즘

1. 패턴 문자열에 대해 접두사이면서 접미사인최대 문자열 개수 구하기

2. 문자열과 패턴을 비교하기 (위 : 문자열, 아래 : 패턴)

3. 다른 부분이 있다면 해당 위치에서 접두사와 접미사가 동일한 만큼 이동시킴

처음부분과 끝부분이 4개 동일하다는 것을 알고 있으므로 이동시킨만큼은 항상 같다

코드

1. 접두사 접미사가 일치하는 최대 길이 배열 구하기

// KMP 전통적인 방법
vector<int> pi(pattern.size()); // prefix index
int begin = 1, matched = 0;
while (begin + matched < pattern.size()) {
    if (pattern[matched] == pattern[begin + matched]) { // 처음 문자와 끝 문자가 같은지 비교
        ++matched; // 같으면 하나 더해줌
        pi[begin + matched - 1] = matched; // 인덱스에 match 값 기록
    } else {
        if (matched == 0) ++begin; // 하나도 일치하지 않으면 시작지점을 더해줌
        else {
            begin += matched - pi[matched - 1]; // 일부 일치하지 않으면 일치했던만큼 건너뛰기 (KMP탐색의 원리 이용)
            matched = pi[matched - 1]; 
        }
    }
}

// KMP 응용
vector<int> pi(P.size());
int matched = 0;
for (int i = 1; i < P.size(); i++) { // i는 begin + matched에 해당
    while (matched > 0 && P[i] != P[matched]) matched = pi[matched - 1]; // 현재 문자가 다르면 matched를 pi[matched - 1]로
    if (P[i] == P[matched]) pi[i] = ++matched; // 동일하면  matched를 1 더해줌
}

 

2. 문자열과 패턴 비교

// KMP 전통적인 방법
vector<int> res;
begin = 0, matched = 0;
while (begin <= str.size() - pattern.size()) { // 시작부분이 남은 문자열보다 많을때 까지만 실행
    if (matched < pattern.size() && str[begin + matched] == pattern[matched]) { // pattern 크기보다 matched 크기가 작고(불일치), 현재 문자가 일치할 때
        ++matched; // 일치하므로 match 1만큼 더해줌
        if (matched == pattern.size()) res.push_back(begin); // 패턴크기랑 동일하면 완전히 일치하므로 결과에 추가
    } else { // 현재 문자가 일치하지 않을 때,
        if (matched == 0) ++begin; // 일치하는 부분이 하나도 없다면 시작부분을 1 더해줌
        else { // 일부 일치하면 접두사 접미사가 일치하는 만큼 시작부분을 옮겨줌
            begin += matched - pi[matched - 1];
            matched = pi[matched - 1]; // 일치하는 만큼 matched를 설정
        }
    }
}

// KMP 응용
matched = 0;
for (int i = 0; i < S.size(); i++) { // i는 begin + matched에 해당
    while (matched > 0 && S[i] != P[matched]) matched = pi[matched - 1]; // 현재 문자가 다르면 matched를 pi[matched - 1]로
    if (S[i] == P[matched]) ++matched; // 동일하면  matched를 1 더해줌
    if (matched == P.size()) { // 이때 패턴 개수와 동일하면 문자열을 발견
        res.push_back(begin);
    }
}

시간복잡도

O(패턴 + 문자열)