KMP 알고리즘 - next 배열 의 이해
1509 단어 데이터 구조
최근 에는 데이터 구 조 를 학습 하면 서 KMP 알고리즘 을 배 웠 다.처음에는 KMP 알고리즘 의 목적 만 알 았 는데, 패턴 문자열 을 오른쪽으로 최대한 멀리 미 끄 러 뜨리 고 알고리즘 의 목적 도 이해 하 는 것 이 었 다.그러나 그 중 next 배열 의 의미 와 구 해 는 잘 모른다.한 번 의 사 고 를 통 해 문득 크게 깨 달 았 는데, 여기에 기록 하고 나 누 어 보 자.
next 배열 의 의미
먼저 제 가 이해 하기 쉽다 고 생각 하 는 설명 을 붙 여 주세요. KMP 알고리즘 을 어떻게 잘 이해 하고 파악 하 는 지.
KMP 알고리즘 의 핵심 은 부분 일치 표 (Partial Match Table) 라 고 불 리 는 배열 입 니 다.(상기 대답 참조)
next 배열 은 길이 가 n (패턴 문자열 의 길이) 인 배열 입 니 다.
next 배열 의 아래 표 시 는 패턴 문자열 의 하위 문자열 의 길 이 를 대표 합 니 다. 하위 문자열 의 길 이 는 0 이 될 수 없 기 때문에 next 배열 의 의미 있 는 수 치 는 next [1] 에서 시 작 된 것 입 니 다. n - 1 까지, 즉 최대 하위 문자열 의 길이 입 니 다.
next 배열 의 요소: 위의 링크 에서 설명 한 바 와 같이 next 배열 에 기 록 된 것 은 하위 문자열 정보 입 니 다. 길이 가 1 인 하위 문자열 부터 n - 1 하위 문자열 이 끝 날 때 까지 접두사 의 최대 공공 문자열 의 길 이 를 기록 합 니 다.
위 에서 말 한 바 와 결합 하여 우 리 는 각 하위 문자열 의 앞 접미사 의 최대 공공 하위 문자열 길 이 를 계산 한 후 next [1] 에서 next [n - 1] 까지 의 요소 에 놓 고 next [0] 의 위치 에 놓 습 니 다 - 1.이렇게 하면 일부 글 에서 말 하 는 가장 큰 공공 문자열 의 길 이 를 '오른쪽으로 이동' 하 는 이유 이다.
next 배열 에 무엇 을 넣 었 는 지 알 면 계산 할 수 있 습 니 다.
void get_next(string s, int next[]) {
size_t len = s.length();
//
int i = 0;
int j = -1;
next[0] = -1;
// len - 1 ， 1 len-1
while (i < len - 1) {
// ， ， ，
if (j == -1 || s[i] == s[j]) {
++i;
++j;
next[i] = j;
}
// ， i
else
j = next[j];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
