데이터 구조의 문자열 패턴 일치 알고리즘 (KMP)

여기 서 먼저 제 가 참고 한 블 로그 사이트 와 참고 한 책 은 데이터 구조 (엄 울 민) 입 니 다.
참조 코드 의 사이트 주소
여기 서 나 는 나의 생각 을 정리 해 보 겠 다.
먼저 기본 개념 을 소개 하 다

메 인 문자열: 일치 하 는 문자열

을 말 합 니 다.

모드 문자열: 메 인 문자열 에서 찾 아야 할 문자열

KMP 매 칭 알고리즘 은 패턴 문자열 자체 의 중복 부분 을 이용 하여 매 칭 에서 중복 되 는 매 칭 과정 을 없 애 는 데 중점 을 둔다.

아래 약속

문자열 과 next 배열 의 아래 표 시 는 1 부터 (인위적인 규정)

i 는 메 인 문자열 을 가리 키 는 지침 이 고 j 와 k 는 모드 문자열 을 가리 키 는 지침

T 는 모드 문자열 그룹 을 대표 하고 S 는 메 인 문자열 그룹

을 대표 한다.

= = 좌우 가 같다 는 뜻,! =좌우 가 같 지 않다 는 뜻

next 배열 의 풀이

next[1] = 0

우 리 는 next 배열 의 첫 번 째 위치 값 이 0 이 라 고 약속 합 니 다. 모드 문자열 의 첫 번 째 문자 가 일치 하지 않 는 다 는 것 을 의미 합 니 다. 이때 메 인 문자열 의 현재 일치 하지 않 는 문자 의 다음 문자 부터 다시 일치 합 니 다 (i 증가 1). 모드 문자열 도 물론 처음부터 시작 합 니 다 (j 는 1).

다음 [j] = k

그래서 'T [1]... T [k - 1]' = 'T [j - k + 1]... T [j - 1]'
위 에 표 시 된 패턴 문자열 의 접두사 길 이 는 k - 1 인 문자열 과 j 에서 k - 1 길 이 를 앞 세 는 문자열 이 같 습 니 다.
이때 두 가지 상황 이 발생 한다.
첫 번 째: T [k] = T [j]
그래서 'T [1]... T [k] =' T [j - k + 1]... T [j] 는 'T [1]... T [1]' = 'T [j - k + 1]... T [j - 1]' 때 next [j] = k 그래서 'T [1]... T [k] =' T [j - k + 1]... T [j] '때 next [j + 1] = k + 1 = next [j] + 1
만약 S [i]! =T [j], 패턴 문자열 의 j 번 째 문자 가 어 울 리 지 않 으 면 우 리 는 S [i] 와 T [next [j] 를 비교 하 게 할 것 이다. 그러나 우 리 는 첫 번 째 상황 인 T [next [j] = = T [j] 이기 때문에 당연히 S [i] 와 같 지 않다. 이것 은 한 번 의 헛 된 일 을 한 것 과 같다.
그래서 위의 판단 에 하나의 판단 을 더 해 야 한다. 만약 에 T [k + 1] = T [j + 1] 라면 next [j + 1] = next [k + 1], 그렇지 않 으 면 next [j + 1] = k + 1
여기 서 예 를 들 어 모드 꼬치 ABAB 는 k 가 첫 번 째 위치 A 를 가리 키 고 j 가 세 번 째 위치 A 를 가리 키 면 둘 이 똑 같 습 니 다. 원래 next [j + 1] = 2 를 직접 할당 하 였 으 나 T [k + 1] = T [j + 1] 때문에 next [j + 1] = next [k + 1] = 1 로 바 꾸 었 습 니 다.원래 ABAB 의 next 배열 은 0112 였 으 나 지금 은 0101 로 바 뀌 었 다.
두 번 째: T [k]! =T[j]
예 를 들 어 모드 문자열 abacdababc, 그 중 k 는 4, j 는 9 입 니 다.각각 캡 처 해 보면 abac 와 abab 입 니 다.
왜냐하면: T [k]! =T [j] 는 abac 의 앞 에 있 는 a 와 abab 의 꼴찌 두 번 째 a 가 같 으 면 abac 의 두 번 째 b 부터 비교 할 수 있 음 을 알 수 있 습 니 다. 그래서 여 기 는 k 를 2 즉 k = next [k] 로 바 꾸 고 abac 의 두 번 째 와 abab 의 마지막 요 소 를 비교 하면 됩 니 다.다시 T [k] 와 비교 하면 T [j + 1] = next [k] + 1;그렇지 않 으 면 j = next [j] 를 j = next [1] = 0 까지 다시 실행 합 니 다. 이렇게 T [j + 1] = next [1] + 1 = 1
요약 하면:

T[1]…T[k]’ == ‘T[j-k+1]…T[j]，next[j] = k;

1 의 조건 하에 서

T [k] = = T [j] 와 T [k + 1] = = T [j + 1], next [j + 1] = next [k + 1]

T [k] = = T [j] 그리고 T [k + 1]! =T[j+1]，next[j+1] = k+1

T[k]!=T[j]，k = next[k]

next[1] = 0

수학의 정리 처럼 한 걸음 한 걸음 밀 어 낼 수 있 기 때문에 공식 으로 생각 하거나 이미지 기억 으로 바 꿔 도 된다.
상술 한 분석 을 종합 하면 절차 적 사고방식 을 얻어 낼 수 있다

j 를 1 지향 모드 문자열 의 첫 번 째 요소 로 설정 하고 k 는 0 으로 모드 문자열 의 첫 번 째 부터 비교 하 는 것 을 나타 내 며 next 배열 의 첫 번 째 위 는 0

이다.

다음은 당연히 전체 패턴 을 순환 적 으로 옮 겨 다 니 는 것 이다.

두 가지 판단 조건 k 가 0 인지, T [k] 가 T [j] 인지, k 가 0 인지 다시 처음부터 일치 하 는 지 를 나타 내 면 k 와 j 를 직접 1 로 늘린다.만약 에 T [k] 가 T [j] 와 같 고 T [k + 1] = T [j + 1] 는 next [j + 1] = next [k + 1] 과 같 지 않 으 면 정상 적 인 방법 으로 next [j + 1] = k + 1 을 나타 낸다.

매번 의 판단 은 next [j + 1] 의 값 을 구하 기 위해 서 이다. 그래서 여기 j 는 1 을 늘 려 야 한다. k 증 1 앞에서 이미 말 했다

그렇지 않 으 면 k = next [k] 의 경우

개선 전과 개선 후의 c 언어 코드 를 드 리 겠 습 니 다.
개선 전 코드

void get_next(SString T, int next[]){
    int j = 1;
    int k = 0;
    next[1] = 0;

    while(j<T[0]){
        if(k==0 || T[j]==T[i]){
            j++;
            k++;
            next[j] = k;
        }else{
            k = next[k];
        }
    }

    return;
}

개 선 된 후의

void get_nextval(SString T, int nextval[]){
    int j = 1;
    int k = 0;
    next[1] = 0;

    while(j<T[0]){
        if(k==0 || T[k]==T[j]){
            j++;
            k++;
            if(T[k]!=T[j]){
                nextval[j] = k;
            }else{
                nextval[j] = nextval[k];
            }
        }else{
            k = next[k];
        }
    }

    return;
}