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

컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(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알고리즘 실행중, 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재이다.

문자열 검색 알고리즘
도널드 커누스
1970년 컴퓨팅