[Algorithm] 문자열 매칭 알고리즘

문자열 알고리즘

특정한 글이 있을 때, 그 글안에서 특정한 문자열을 찾는 알고리즘이다.

단순 문자열 알고리즘

단순히 하나씩 비교하는 가장 간단한 형태의 알고리즘이다.

찾을 문자열을 전체 문장의 처음부분에 두고, 하나씩 비교한다.
일치할 때 까지, 한 칸씩 이동하며 비교한다.

구현

시간 복잡도는 '찾을 문자열의 길이' 곱하기 '전체 index' 로 O(N * M)이다.

#include <iostream>

using namespace std;

int findString(string parent, string pattern) {
    int parentSize = parent.size(); // 전체 문자열 길이
    int patternSize = pattern.size(); // 찾으려는 문자열 길이

    for(int i=0;i<=parentSize - patternSize;i++) {
        bool finded = true;

        for(int j=0;j<patternSize;j++) {
            if(parent[i+j] != pattern[j]) {
                finded = false;
                break;
            }
        }

        if(finded) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    string parent = "Hello World";
    string pattern = "o Wor";

    int result = findString(parent, pattern);

    if(result == -1) {
        printf("찾을 수 없습니다.\n");
    } else {
        printf("%d번 째에서 찾았습니다\n", result+1);
    }
    return 0;
}

KMP 알고리즘

Knuth-Morris-Pratt의 약자이며, 대표적인 문자열 매칭 알고리즘이다.

모든 경우를 다 비교하지 않아도, 부분 문자열을 찾을 수 있는 알고리즘이다.

접두사, 접미사를 이용하여 불필요한 연산은 스킵하여 연산을 줄인다.

접두사와 접미사가 최대로 일치하는 만큼 점프할 수 있다.

접두사 접미사 비교하기

패턴 문자열의 첫 번째와, 두 번째에 각각 j,i를 일치시킨다.

j와 i를 비교하여, 두 문자가 같으면 i 인덱스의 값으로 j 인덱스 + 1을 넣어주고, j와i의 index를 둘 다 증가시킨다.

j가 0인경우 일치하지 않으면 i를 증가시켜 비교한다.

만약, j가 0보다 큰데, 일치하지 않는 경우, j를 한 칸 뒤로 이동시켜 비교한다.

인덱스의 값이 접두사와 접미사의 최대일치 길이이다.

#include <iostream>
#include <vector>

using namespace std;

// 실패함수 구현(접두사와 접미사 최대 일치 길이 비교)
vector<int> makeTable(string pattern) {
    int patternSize = pattern.size();

    vector<int> table(patternSize, 0);

    int j=0;
    for(int i=1;i<patternSize;i++) {

        // j 인덱스가 0이상인데, i번째와 j번째 문자가 일치하지 않는다면, 
        while(j>0&&pattern[i]!=pattern[j]) {
            j = table[j-1]; // 한 칸 뒤로 백 
        }

        if(pattern[i]==pattern[j]) {
            table[i] = ++j;
        }
    }

    return table;
}

int main(void) {
    string pattern = "abacaaba";
    vector<int> table = makeTable(pattern);
    for(int i=0;i<table.size();i++) {
        printf("%d ", table[i]);
    }
    return 0;
}

KMP 알고리즘 원리

(*접두사, 접미사를 비교한 테이블이 존재해야한다.)

전체 문자열과, 패턴 문자열을 하나씩 비교한다.

일치하지 않은 경우가 발생하면, 일치하는 부분은 건너뛰고, 다시 확인한다.

즉, 문자열 매칭에서 실패한 부분에서 1을 뺀 값이 가리키는 값(접두사, 접미사 일치 테이블에서)까지는 일치를 했다는 뜻.그 값으로 j를 이동시켜서 다시 확인하는 것이다.

KMP 구현

시간복잡도는 거의 전체 문자열의 길이만큼만 비교하면 되기때문에 O(N)에 가깝다.

#include <iostream>
#include <vector>

using namespace std;

// 실패함수 구현(접두사와 접미사 최대 일치 길이 비교)
vector<int> makeTable(string pattern) {
    int patternSize = pattern.size();

    vector<int> table(patternSize, 0);

    int j=0;
    for(int i=1;i<patternSize;i++) {

        // j 인덱스가 0이상인데, i번째와 j번째 문자가 일치하지 않는다면, 
        while(j>0&&pattern[i]!=pattern[j]) {
            j = table[j-1]; // 한 칸 뒤로 백 
        }

        if(pattern[i]==pattern[j]) {
            table[i] = ++j;
        }
    }

    return table;
}

void KMP(string parent, string pattern) {
    vector<int> table = makeTable(pattern); 

    int parentSize = parent.size();
    int patternSize = pattern.size();

    int j=0;
    for(int i=0;i<parentSize;i++) {
        while(j>0&&parent[i]!=pattern[j]) {
            j = table[j-1]; // 일치 하지 않았을 때, 이전 단계에 있던 값으로 이동 
        }

        if(parent[i]==pattern[j]) {
            if(j==patternSize-1) {
                printf("%d번 째에서 찾았습니다\n", i - patternSize +2);
                j = table[j]; // 찾았어도 다음에 또 일치할 수 있기 때문에 점프
            } else {
                j++; // 단순히 매칭만 이루어졌기 때문에 j만 증가시켜 매칭 확인 
            }
        }
    }
}

int main(void) {
    string parent="abacaabaqweabacaabaqww";
    string pattern = "abacaaba";
    KMP(parent, pattern);
    return 0;
}

reference: https://www.youtube.com/watch?v=yWWbLrV4PZ8&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=34