16. KMP 문자열 매칭

단순 비교 문자열 매칭

• 단순 비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교
• 단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도 가짐

단순 비교 문자열 과정

단순 비교 문자열 구현

#include <stdio.h>
#include <string.h>

// 단순 비교 문자열 매칭
char* parent = "ABCDEFG";
char* pattern = "EF";

// main
int main(void) {
    int parentSize = strlen(parent);
    int patternSize = strlen(pattern);

    for (int i = 0;i <= parentSize - patternSize;i++) {
        int found = 1;
        for (int j = 0;j < patternSize;j++) {
            if (parent[i + j] != pattern[j]) {
                found = 0;
                break;
            }
        }
        if (found) {
            printf("%d번째에서 찾았습니다.\n", i + 1);
        }
    }

    system("pause");
    return 0;
}

KMP 문자열 매칭

• KMP 문자열 매칭 알고리즘 사용 시 O(N+M)의 시간 복잡도로 해결 가능
• 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행

KMP 문자열 매칭 과정

문자열 테이블 만들기

문자열 매칭 진행하기

KMP 문자열 매칭 구현

#define _CRT_SECURE_NO_WARNINGS_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* parent = "acabacdabac";
char* pattern = "abacdab";

// 테이블 만들기
int* makeTable(char* pattern) {
    int patternSize = strlen(pattern);
    int* table = (int*)malloc(sizeof(int) * patternSize);

    for (int i = 0;i < patternSize;i++) {
        table[i] = 0;
    }
    int j = 0;
    for (int i = 1;i < patternSize;i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = table[j - i];
        }
        if (pattern[i] == pattern[j]) {
            table[i] = ++j;
        }
    }
    return table;
}

// KMP
void KMP(char* parent, char* pattern) {
    int* table = makeTable(pattern);
    int parentSize = strlen(parent);
    int patternSize = strlen(pattern);
    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++;
            }
        }
    }
}

// main
int main(void) {
    KMP(parent, pattern);

    system("pause");
    return 0;
}