Data-Structure - Arrays and Structure

KMP Pattern Matching

이 KMP패턴 매칭 문제는 비교한 정보를 최대한 활용하자는 취지에서 나타난 알고리즘입니다.

먼저 pattern에 해당하는 failure함수를 작성해 주어야 합니다. failure 함수는 접두사를 활용합니다. 이는 maximum length - 1 of the prefix and suffix that matches in the partial patterns으로 정의됩니다.

 

즉 j = 4일 때 위의 예시에서 "abcab"인데 -> ab c ab로 나눌 수 있고 |ab| - 1은 1이기 때문에 failure[4] = 1이 됩니다.

비슷하게 j = 5일 때는 "abcabc"인데 -> abc abc로 나눌 수 있고 ( 겹치는 부분 허용 ) |abc| - 1은 2이기 때문에 failure[5] = 2이 됩니다. 이외에 겹치지 않는 부분은 -1로 초기화 해 주시면 됩니다.

 

이 failure함수는 KMP Pattern Matching에 핵심적인 역할이 됩니다. 위의 예시에서 보면 string과 pat이 index 3에서 어긋나기 시작했습니다. 그러면 pat의 비교하는 부분을 failure[3 - 1] + 1부터 시작하면 됩니다. 즉 위의 첫번쨰 어긋나는 경우에서는 failure[2] + 1 = 0이므로 앞에서 비교한 abc가 같다는 것을 활용해서 다시 비교를 하기 시작합니다.

 

근데 바로 또 string은 b로 pat은 a로 충돌이 났습니다. 이러한 경우에는 예외처리를 해주어서 pat은 그대로 두고 string을 한칸씩 땡겨서 b가 아닌 그 다음 문자인 a부터 pat와 비교하기 시작하게 처리해 주면 됩니다.

 

이렇게 반복하다가 string의 인덱스가 초과하기 시작하거나 string안에서 pat이 찾아진 경우에는 이에 pat이 시작되는 index를 반환해 주면 됩니다.

 

이를 c언어로 구현한 코드는 아래와 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_SiZE 1000
int *failureArr;
// failure함수에는 패턴이 일단 있어야 한다.
// 처음으로 맞지 않는 값을 제공해 줘야 한다.
void failure(char *patString)
{
 
    int n = strlen(patString);
    failureArr[0] = -1;
    int i, j;
    for (j = 1; j < n; j++)
    {
        i = failureArr[j - 1];
        while ((patString[j] != patString[i + 1]) && (i >= 0))
        {
            i = failureArr[i];
        }
 
        if (patString[j] == patString[i + 1])
        {
            failureArr[j] = i + 1;
        }
        else
        {
            failureArr[j] = -1;
        }
    }
 
    printf("Failure function:\n");
    for (j = 0; j < n; j++)
    {
        if (j == 0)
        {
            printf("j\t%d", j);
        }
        else
        {
            printf("\t%d", j);
        }
    }
    putchar('\n');
 
    for (j = 0; j < n; j++)
    {
        if (j == 0)
        {
            printf("pat\t%c", patString[j]);
        }
        else
        {
            printf("\t%c", patString[j]);
        }
    }
 
    putchar('\n');
    for (j = 0; j < n; j++)
    {
        if (j == 0)
        {
            printf("f\t%d", failureArr[j]);
        }
        else
        {
            printf("\t%d", failureArr[j]);
        }
    }
    putchar('\n');
}
 
void failure2(char *patString, int *failureArr)
{
    failureArr[0] = -1;
    for (int i = 0, j = 1, status = -1; patString[j] != '\0'; ++j)
    {
        if (patString[i] != patString[j])
        {
            i = 0;
            status = -1;
            failureArr[j] = status;
        }
        else
        {
            i++;
            status++;
            failureArr[j] = status;
        }
    }
    for (int i = 0; i < strlen(patString); i++)
    {
        printf("%d ", failureArr[i]);
    }
}
 
int pmatch(char *string, char *pat)
{
    int i = 0, j = 0;
    int lens = strlen(string);
    int lenp = strlen(pat);
 
    while (i < lens && j < lenp)
    {
        if (string[i] == pat[j])
        {
            i++;
            j++;
        }
        else if (j == 0)
        {
            i++;
        }
        else
        {
            j = failureArr[j - 1] + 1;
        }
    }
 
    return ((j == lenp) ? (i - lenp) : -1);
}
 
int main(void)
{
    FILE *fp_read;
    fp_read = fopen("input.txt", "r");
 
    char firstString[MAX_SiZE] = {0};
    char secondString[MAX_SiZE] = {0};
 
    failureArr = malloc(sizeof(int) * strlen(secondString));
 
    fscanf(fp_read, "%s %s", firstString, secondString);
 
    // failure2(secondString, failureArr);
    failure(secondString);
    printf("The pattern %s is found at the position %d", secondString, pmatch(firstString, secondString));
 
    fclose(fp_read);
 
    return 0;
}

abcabcabaaabcabcabccabcabcabcdabcabcabcaa
abcabcabca

위의 예제에서 사용한 input.txt파일의 내용입니다.