본문으로 이동

커누스-모리스-프랫 알고리즘

위키백과, 우리 모두의 백과사전.

컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다.

문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi)를 사용한다.

vector<int> KMP_GET(string grope){
    int Begin=0, Length = (int)grope.size();
    vector<int> pi(Length, 0);
    for(int i=1 ; i< Length ; i++){
        while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1];
        if(grope[i] == grope[Begin]) pi[i] = ++Begin;
    }
    return pi;
}

위는 실패함수를 계산하는 코드이다. 위 코드로 나온 pi배열 KMP알고리즘 실행중, 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재이다.