[BOJ_16172_RN] 나는 친구가 적다 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/16172

문제 해결에 필요한 알고리즘 : KMP ( Knuth Morris Pratt ) 알고리즘

해설

알파벳과 숫자로 이루어진 문자열에서 숫자를 무시하고 검색하여 문자열이 포함되어있는지 판단하는 문제이다. 문자열 길이가 1,000,000 이므로 일반적인 탐색방법으로는 해결이 불가하다. 그래서 빠른 검색알고리즘인 KMP를 적용하면 된다.

KMP 알고리즘은 한번의 순회로 문자열을 검색하는 방법이다.

간단한 예시로

nabananbananaba 라는 문자열에서 nanaba를 검색한다고 했을 때 일반적인 알고리즘이라면 첫 na까지 검색하고 b가나와 맞지않으므로 a부터 검색을 시작한다. 하지만 이미 na까지 검색을 했다면 a로 탐색을 시작하면 안된다는 것을 알고있다. 그래서 이런 과정을 생략해주는것이 KMP알고리즘이다. 이 알고리즘에 필요한 것은 검색하기 전 몇개의 문자가 일치하고 실패했을 때, 다시 검색할 때 현재의 위치에서 몇개의 문자가 일치하는지 갯수를 기록해 주어야 한다. 코드에서 getPi가 미리 전처리해주는 부분이다.

예를들어 nana를 검색하고 검색에 실패했다면 다시 돌아와서 검색을 하는것이 아닌 na라는 검색이 성공했다고 생각하고 검색중인 인덱스부터 다시 검색을 하는 기법이다. 위의 문자열에서 5번째 글자부터 nan을 검색했다고 했을 때 다음글자는 a가나와야하는데 b이므로 검색이 실패했다 이 때 nan을 검색했다면 다시 6번째인 a로 돌아와 검색을 하는것이 아니라 8번째인 b부터 검색하되 현재 n까지 일치했다고 생각하고 검색을 재개하는것이다. 이렇게 검색을 하면 빠른 검색이 가능하다.

시간복잡도

N : 주어진 문자열

M : 검색할 문자열

getPi함수의 전처리 할 때는  의 시간이 걸린다. 또 KMP 함수는  만큼 걸린다.

따라서 KMP 알고리즘의 시간복잡도는  이다.

나는 친구가 적다 코드 [ C ]

#include <string.h>
#include <stdio.h>
char dst[1000001], src[1000001];
int pi[1000001];
void getPi(int dlen) {
    int mat = 0, i;
    for (i = 1; i < dlen; ++i) {
        if (dst[i] == dst[mat]) {
            pi[i] = ++mat;
        } else if (mat) {
            mat = pi[mat - 1];
            --i;
        }
    }
}
int kmp(int dlen, int slen) {
    int mat = 0, i;
    for (i = 0; i < dlen; ++i) {
        if (dst[i] >= '0' && dst[i] <= '9') continue;
        if (dst[i] == src[mat]) {
            ++mat;
        } else if (mat) {
            mat = pi[mat - 1];
            --i;
        }
        if (mat == slen) return 1;
    }
    return 0;
}
int main() {
    int dlen, slen;
    gets(dst);
    gets(src);
    dlen = strlen(dst);
    slen = strlen(src);

    getPi(dlen);
    printf("%d", kmp(dlen, slen));
    return 0;
}