KMP 알고리즘 을 자세히 해석 하고 KMP 를 이해 하고 기억 합 니 다.

요 며칠 동안 많은 사람들 이 설명 하 는 KMP 알고리즘 을 보 았 습 니 다. 모두 가 말 하 는 것 이 다 릅 니 다. 기억 을 이해 하기 쉬 운 사고방식 을 정리 하고 KMP 알고리즘 을 철저히 해 결 했 습 니 다.!!
KMP 알고리즘 은 문자열 패턴 일치 문 제 를 해결 하 는 것 입 니 다.먼저 검색 할 문자열 은 S 이 고 길 이 는 n 이 며 일치 하 는 문자열 은 M 이 며 길 이 는 m 입 니 다.
그러면 KMP 를 직관 적 으로 이해 하고 다른 사람의 설명 을 요약 하면 다음 과 같다.
먼저 몇 가지 개념 을 소개 한다.
1. 접두사, 접두사 (접두사 와 접 두 사 는 모두 문자열 입 니 다. 원래 의 전체 문자열 은 포함 되 지 않 습 니 다)
2. 부분 일치 표
'부분 일치 값' 은 '접두사' 와 '접두사' 의 가장 긴 공유 요소 의 길이 입 니 다."ABCDABD" 를 예 로 들 면,
- "A" 의 접두사 와 접 두 사 는 모두 빈 집합 이 고 모두 요소 의 길 이 는 0 입 니 다.
- "AB" 의 접 두 사 는 [A] 이 고 접 두 사 는 [B] 이 며 모두 요소 의 길 이 는 0 입 니 다.
- "ABC" 의 접 두 사 는 [A, AB] 이 고 접 두 사 는 [BC, C] 이 며 모두 요소 의 길이 가 0 입 니 다.
- "ABCD" 의 접 두 사 는 [A, AB, ABC] 이 고 접 두 사 는 [BCD, CD, D] 이 며 모두 요소 의 길 이 는 0 입 니 다.
－ "ABCDA" 의 접 두 사 는 [A, AB, ABC, ABCD] 이 고 접 두 사 는 [BCDA, CDA, DA, A] 이 며 모두 요소 가 "A" 이 고 길 이 는 1 입 니 다.
－ "ABCDAB" 의 접 두 사 는 [A, AB, ABC, ABC, ABCDA] 이 고 접 두 사 는 [BCDAB, CDAB, DAB, AB, B] 이 며 모두 요소 가 "AB" 이 고 길 이 는 2 입 니 다.
－ "ABCDABD" 의 접 두 사 는 [A, AB, ABC, ABC, ABCDA, ABCDAB] 이 고 접 두 사 는 [BCDABD, CDABD, DABD, ABD, BD, D] 이 며 모두 요소 의 길 이 는 0 입 니 다.
그래서 다음 부분 일치 표 가 생 성 됩 니 다.
3. 이동 걸음 수
위의 그림 에서 보 듯 이 M 의 회색 부분 은 S 의 회색 부분 과 일치 하지만 회색 이 일치 하지 않 으 면 M 은 뒤로 이동 합 니 다. 그림 의 위치 가 S 와 다시 일치 할 때 까지 계속 뒤로 이동 한다 고 가정 하면 그림 의 위치 가 얼마나 이동 할 수 있 습 니까?간단 합 니 다. 이미 일치 하 는 길이 (즉 회색 부분 길이) - A (또는 B) 의 길이 입 니 다. 그러면 A (또는 B) 의 길 이 는 위 에서 소개 한 부분 일치 값 입 니 다.따라서 이동 걸음 수 = 일치 하 는 문자 수 - 일치 하 는 마지막 문자 에 해당 하 는 부분 일치 값 입 니 다.
여기까지 읽 으 면 KMP 알고리즘 을 완전히 이해 해 야 합 니 다.
위의 설명 은 KMP 알고리즘 을 이해 하기 위 한 것 이지 만 위의 사고방식 에 따라 프로 그래 밍 을 하면 매우 복잡 하기 때문에 프로 그래 밍 이 실 현 될 때 우 리 는 약간의 변 화 를 추가 합 니 다!
next [i] 의 값 은 가장 긴 접두사 의 다음 위 치 를 나타 낸다.즉, next [i] 의 값 은 가장 긴 일치 문자열 의 길이 입 니 다.i 는 [0,... i] 의 문자열 을 나타 낸다.
j = next [i] 를 설정 하면 회색 부분 은 이 두 단락 의 문자 가 같다 는 것 을 나타 낸다. 만약 에 i 위치의 문자 와 j 위치의 문자 가 같다 면 next [i + 1] = j + 1;앞의 회색 부분 과 j 위치의 문자 로 구 성 된 문자열 과 뒤의 회색 과 i 연결 로 구 성 된 문자열 이 같 기 때문이다.이것 이 바로 앞의 next 배열 에 대한 정의 입 니 다.같 지 않 으 면 i 부터 i 를 포함 한 문자열 이 0 부터 시작 하 는 문자열 과 같 아서 같은 접두사 와 접 두 사 를 만들어 야 합 니 다.다행히 우 리 는 next [next [i] 의 값 을 알 고 있 습 니 다. next [i] 앞의 문자열 에 도 가장 긴 공공 접두사 와 접두사 가 있 기 때 문 입 니 다. 이 공공 접 두 사 는 현재 i 와 앞으로 형 성 된 문자열 과 같 을 수 있 습 니 다. 이렇게 계속 앞으로 찾 을 수 있 습 니 다. 찾 지 못 하면 i 위치의 문자 가 이전에 나타 나 지 않 았 음 을 설명 합 니 다.
이렇게 구 한 next 배열 은 아래 표 1 에서 시 작 된 것 입 니 다. 아래 표 0 전에는 빈 문자열 이 고, 아래 표 1 은 M 문자열 의 0 번 째 문자 에 대응 하기 때 문 입 니 다.우 리 는 next [0] = - 1 을 설정 합 니 다. 단지 표지 일 뿐 특별한 의미 가 없습니다.
그러면 앞에서 말 한 바 와 같이 next 배열 을 초기 화 하 는 코드 를 쉽게 쓸 수 있 습 니 다.

void getNext(char *str,int *next){
        int len=strlen(str);
        if(len==0){
            return;
        }
        next[0]=0;
        for(int i=1;i0&&str[i]!=str[j]){
                j=next[j-1];
            }
            if(str[i]==str[j]){
                next[i]=j+1;
            }else{
                next[i]=0;
            }
        }
    }

next 를 알 게 되면 kmp 검색 은 상대 적 으로 간단 합 니 다. 즉, 일치 하지 않 으 면 next 배열 을 조회 하면 됩 니 다.

int KMP(const char *str, const char *dest) {
	int slen = strlen(str);
	int dlen = strlen(dest);
	int i = 0, j = 0;
	int *next = new int[dlen];
	getNext(dest, next);
	while (i < slen && j < dlen) {
		if ( str[i] == dest[j]) {
			i++;
			j++;
		} else if(j==0){

			i++;

		}else{
			j = next[j-1];
		}
	}
	if (j == dlen) {
		return i - j;
	} else {
		return -1;
	}
}

KMP 알고리즘 의 시간 복잡 도 는 O (n + m)
참고:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://chaoswork.com/blog/2011/06/14/kmp%E7%AE%97%E6%B3%95%E5%B0%8F%E7%BB%93/