Pattern matching, KMP algorithm

자료구조를 복습하느라 자료구조 책을 오랜만에 다시 펴봤다.

그러다 KMP algorithm이 눈에 들어왔다.

중간고사때 완벽히 풀어내지 못했던 기억이 새록새록 떠올랐다..

자료구조 수강 당시 완전 돌이었고(지금도 돌이지만) algorithm 이 많이 약하기 때문에 다시 봐야겠다고 생각했다.

우리가 string에서 어떤 pattern 이 있는지, 그 위치는 어딘지 구하려면 어떤 방식으로 구현할까

가장 쉬운방법은 brute force로 string[s_0] 부터 진행하면서 pattern과 일치하는지 비교하고 중간에 일치하지 않는다면 string[s_1] 부터 다시 비교를 시작하는 것이다.

이런식으로 구현을 한다면 시간 복잡도는 O(n*m) 이 된다는 것을 쉽게 생각할 수 있다.

이런 방식의 비효율은 어디서 발생할까.

string[i] 에서부터 시작해 string[i+n] 까지 이미 비교를 했음에도 불구하고 no match 가 발생하면 string[i+1] 로 돌아가 다시 비교를 한다는 점이다.

이를 개선한 방법이 KMP algorithm이다.

    int pmatch(char *string, char* pattern) {
        int i = 0, j = 0;
        int s_len = strlen(string);
        int p_len = strlen(pattern);

        while (i < s_len && j < p_len) {
            if (string[i] == pattern[j]) {
                i++; j++;
            }
            else if (j == 0) i++;
            else j = failure[j - 1] + 1;
        }
        return ((j == p_len) ? (i - p_len) : -1);
    }
   void fail(char *pattern) {
        int len = strlen(pattern);

        failure[0] = -1;
        for (int j = 1; j < len; j++) {
            int i = failure[j - 1];
            while ((pattern[j] != pattern[i + 1]) && (i >= 0))
                i = failure[i];
            if (pattern[j] == pattern[i + 1])
                failure[j] = i + 1;
            else
                failure[j] = -1;
        }
    }
   int main()
    {
        char string[MAX_STRING_LEN];
        char pattern[MAX_PATTERN_LEN];

        fscanf(stdin, "%s", string);
        fscanf(stdin, "%s", pattern);

        fail(pattern);
        pmatch(string,pattern);

        return 0;
    }

• 중요한 것은 fail 함수이다.