KMP 알고리즘 은 정말 간단 합 니 다.

KMP 알고리즘 은 정말 간단 합 니 다.
KMP 는 문자열 이 일치 하 는 대표 적 인 알고리즘 으로 한때 경원 하 다가 정확 한 KMP 알고리즘 을 쓰기 어 려 웠 습 니 다. 이것 은 모두 '교과서' 덕분에 교수 님 들 에 게 KMP 가 어렵 다 는 느낌 이 들 었 습 니 다!
사실 KMP 알고리즘 을 이해 하 는 것 은 매우 간단 합 니 다. 오늘 은 끝까지 살 펴 보 겠 습 니 다. 제 목 표 는 몇 가지 간단 한 수학 등식 에서 KMP 알고리즘 을 유도 하 는 것 입 니 다. 간단 하지만 엄밀 합 니 다.
직렬 일치
먼저 문자열 이 일치 하 는 장면 을 회상 해 보 세 요. 두 문자열 의 S 와 T 를 지정 한 다음 에 S 문자열 에서 T 문자열 을 찾 습 니 다. 성공 하면 일치 하 는 것 입 니 다. 그렇지 않 으 면 일치 하지 않 습 니 다.예 를 들 면:
S = “avantar-titanic”; T = “avantar”; C = “tistan” ；그러면 결 과 는 T 가 S 와 일치 하고 C 는 S 와 일치 하지 않 는 다.
소박 한 문자열 일치 알고리즘
다시 한 번 소박 한 매 칭 사상 을 돌 이 켜 보면 S [i] 부터 S [i + pos] 가 T [pos] 와 같 는 지, S [i + pos] = T [pos] 가 있다 면 pos +;하면, 만약, 만약...T [pos], 그러면 T 는 T [0] 로 되 돌아 간 다음 에 S [i + 1] 부터 T 와 일치 하 는 것 을 시도 해 야 합 니 다. 이것 이 바로 아래 의 위조 코드 입 니 다.

for(int i = 0; i < Len[S]; i++)
{
	int j;
	for(j = 0; j < Len[T]); j++)
	{
		if(S[i+j] != T[j]) break;
	}
	if(j == Len[T])
		find T in S
}

 
위의 알고리즘 의 문 제 는 일치 하지 않 는 상황 이 발생 하면 T 는 T [0] 로 되 돌아 가 야 하고 알고리즘 복잡 도 는 O (len [S] * len [T]) 이다.
처음부터 다시 해 야 합 니까?
위의 문 제 를 다시 살 펴 보고 S 열 에서 T 열 을 찾 습 니 다. 우 리 는 표현법 C [i, j] 를 사용 하여 C 를 표시 하 는 문자열 S i + 1... S j 를 사용 합 니 다.현재 시각 S 가 위치 i 부터 pos 의 길이, 즉 S [i, i + pos - 1] = T [0, pos - 1] 와 일치 하 다 고 가정 하고 계속 아래로 비교 합 니 다.
만약 S [i + pos] = T [pos] 가 있다 면, 여전히 S [i + pos] = T [0, pos] 가 있다.
하면, 만약, 만약...T [pos], 그러면 S [i, i + pos]! =T[0, pos] ；
이때 소박 한 꼬치 매 칭 사상 은 T 에서 T [0] 로 되 돌아 가 S [i + 1] 과 T [0] 부터 다시 한 번 문 자 를 비교 하 는 것 이다.그러나 이 시각 을 자세히 살 펴 보면 우리 가 T 를 T [0] 로 돌려 보 내지 않 고 T [j] 의 위치 로 돌려 보 내 고 S 를 S [i + pos - 1] 의 위치 에 머 무 르 게 하고 만족 시킨다 고 가정 한다.
S[i+pos-j-1, i+pos-1] = T[0, j] -------------------------(1)
그러면 반드시 j < pos - 1, 그리고 S [i + pos] 와 T [j + 1] 부터 문 자 를 비교 하면 더욱 효율 적 이지 않 습 니까?다음은 이 j 를 찾 을 수 있 는 지 살 펴 보 겠 습 니 다.
가설 법 을 사용 하여 j 가 이미 찾 았 다 고 가정 하면 등식 (1) 이 성립 된다.
매 칭 이 S [i + pos] 까지 진행 되면! =T [pos] 시, 우 리 는 이미 S [i, i + pos - 1] = T [0, pos - 1] 이 있 습 니 다. 뒤의 j 문자열 을 가 져 오 면 다음 과 같 습 니 다.
S[i+pos-j, i+pos-1] = T[pos-j, pos-1] ------------------(2)
등식 (1) 과 등식 (2) 에 따라 우 리 는 얻 을 수 있다.
T[pos-j, pos-1] = T[0, j] ----------------------------------(3)
즉, 이런 j 를 찾 으 면 반드시 등식 (3) 을 만족 시 킬 것 이다.그래서 우 리 는 하나의 배열 P 를 사용 하여 모든 pos 에 대응 하 는 j 를 기억 할 수 있다.즉, P [pos] = j 입 니 다. T [pos] 가 일치 하지 않 을 때 T 를 j 로 되 돌려 주 고 S [i + pos] 와 계속 일치 합 니 다.pos 의 범 위 는 0 ~ len [T] 입 니 다.
만약 j = 0 은 S [i + pos - 1] = T [0] = T [pos - 1] 를 의미한다.
만약 이 j 가 존재 하지 않 는 다 면, 이것 은 발생 할 수 있 는 것 입 니 다. 세상 은 항상 이렇게 아름 답지 않 습 니까? 이 때 는 S [i + pos - 1] 을 의미 합 니 다! =T [0], 그러면 우 리 는 S [i + pos] 와 T [0] 부터 일치 할 수 밖 에 없다.
모든 pos 에 대응 하여 대응 하 는 j 를 찾 으 면 위의 소박 한 일치 알고리즘 을 개선 할 수 있 지 않 습 니까?이 결 과 를 배열 next 에 저장 하기 때문에 next 의 정 의 는 다음 과 같다.
next [pos] 는 pos 에서 T [pos] 와 S [m] 가 일치 하지 않 는 다 고 밝 혔 으 나 T [0, next [pos] = S [m - next [pos] - 1, m - 1] 가 성립 되면 T [next [pos] + 1] 곳 으로 되 돌아 가 S [m] 와 일치 해 야 한다 고 밝 혔 다.
이때 일치 하 는 알고리즘 의 논 리 는 아래 와 같다.
If S [i] = T [j] then / / 일치 하면 계속 뒤로
       i++
       j++
       if j = Len[T] then
              find a match position
       endif
else
       loop / / S [i] = T [j] 의 j 를 찾 습 니 다.
              j = next[j]
until S[i] = T[j] or j < 0
if j < 0 then / / j < 0 은 S [i] 를 나타 낸다! =T [0], i + 1 위치 에서 T [0] 일치
       j = -1
endif
i++
       endif
개 선 된 일치 알고리즘
위의 사상 에 따 르 면 우 리 는 알고리즘 에 맞 는 코드 를 쉽게 쓸 수 있다.

    // search T in S
    int tlen = strlen(T);
    int slen = strlen(S);
    for(int i = 0, j = 0; i < slen;)
    {
        if(S[i] == T[j]) //   S[i] S[j]  ，     S[i+1],T[j+1]
        {
            i++;
            j++;
            if(j == tlen) //        
            {
                printf("find [%s] in [%s] at pos %d./n", T, S, i-tlen);
                j = 0; //        
            }
        }
        else //      ，   P    j'
        {
             //       j'  S[i] = T[j']，  j'=-1
            while((j >= 0) && (S[i] != T[j]))
            {
                j = next[j];
            }
            if(j == -1) // j'=-1，  S[i] != T[0]，     S[i+1]    T
            {
                j = 0;
            }
            i++;
        }
    } 

 
계산 next 배열
지금 또 다른 문제 가 생 겼 습 니 다. next 배열 을 어떻게 구 합 니까?앞의 분석 을 통 해 next 배열 은 T 문자열 과 만 관련 이 있다 는 것 을 알 수 있 습 니 다. next 의 정 의 를 다시 한 번 말씀 드 리 겠 습 니 다.
next [pos] 는 pos 에서 T [pos] 와 S [m] 가 일치 하지 않 는 다 고 밝 혔 으 나 T [0, next [pos] = S [m - next [pos] - 1, m - 1] 가 성립 되면 T [next [pos] + 1] 곳 으로 되 돌아 가 S [m] 와 일치 해 야 한다 고 밝 혔 다.
가장 쉬 운 상황 부터 next [0] = - 1, 만약 T [0]! =S [m] 그러면 T [0] 만 해 볼 수 있어 요?S[m+1];
이해 하기 어렵 지 않 습 니 다. 만약 T [0] = T [1] 라면 next [1] = 0, 그렇지 않 으 면 next [1] = - 1;
next [pos] = j 는 T [pos - j, pos - 1] = T [0, j] 를 만족 시 키 기 때문에 강력 한 방법 으로 이 next 배열 을 찾 을 수 있 습 니 다. 효율 이 너무 낮 을 뿐 더 좋 은 방법 이 있 습 니까?
만약 현재 next [0],..., next [pos - 1] 을 알 고 있다 면, 그들의 값 을 통 해 next [pos] 를 계산 할 수 있 습 니까? next [pos - 1] = j 를 가정 합 니 다.
1 만약 T [j + 1] = T [pos] 를 결합 하면 T [pos - j - 1, pos - 1] = T [0, j] 를 알 수 있다.
T[pos-j-1, pos] = T[0, j+1]
그래서 다음 [pos] = j + 1;
2 만약 T [j + 1]! =T [pos], 그러면 T [pos - j - 1, pos]! =T [0, j + 1], 이 럴 때 어떻게 next [pos] 를 구 합 니까?next [pos] = j '를 가정 하고 j' > - 1 이 있 으 면 T [pos - j ', pos] = T [0, j'] 가 있다.
임의의 i < pos - 1, next [i] = p, T [i - p ', i] = T [0, p'] 에 대해 서 는 p '긍정 < j
현재 T [pos - j - 1, pos - 1] = T [0, j] 가 있 습 니 다. 그래서 T [pos - p '- 1, pos - 1] = T [0, p];
T [pos] = T [p '+ 1] 이 라면 T [pos - p' - 1, pos] = T [0, p '+ 1] 을 의미한다.
그래서 다음 [pos] = 다음 [i] + 1;
보아하니 우 리 는 next 배열 을 구 하 는 방법 을 찾 은 것 같 습 니 다. 일치 하 는 알고리즘 과 비슷 한 지 확인 하 십시오. 위조 코드 는 다음 과 같 습 니 다.
next[0] = -1
i = 1
j = - 1 / / j next [0] 부터
/ / i = Len [T] 까지 순환
If T [i] = T [j + 1] then / / 일치 하면 계속 뒤로
       next [i] = j + 1 / / 계산 next [i]
       i++
       j++
else
       loop / / 찾 아서 T [i] = T [j '+ 1] 의 j'
              j = next[j]
until T[i] = T[j] or j < 0
if j < 0 then / / j < 0 은 T [i] = - 1
       next[i] = j = -1
endif
i++
       endif
c + + 코드 는 다음 과 같 습 니 다.

//    next     ，   T        
void _Next(const char *T, int *next, int tlen)
{
    const char *S = T;
    next[0] = -1;
    for(int i = 1, j = -1; i < tlen;)
    {
        if(S[i] == T[j+1])
        {
            next[i] = j+1; //        next[i]
            i++;
            j++;
        }
        else
        {
            while((j >= 0) && (S[i] != T[j+1]))
            {
                j = next[j];
            }
            if(j == -1)
            {
                next[i] = -1;
            }
            i++;
        }
    }
}

 
KMP 일치 알고리즘
KMP 는 소박 한 매 칭 사상 에 비해 일치 하지 않 을 때 T 가 T [0] 로 되 돌아 갈 필요 가 없어 매 칭 효율 을 높 인 다 는 것 이다.
위의 코드 는 비슷 한 것 같 습 니 다. 사실은 KMP 일치 알고리즘 입 니 다. 코드 논 리 를 간단하게 조정 하면 흔히 볼 수 있 는 KMP 알고리즘 과 비슷 합 니 다.
KMP 알고리즘 은 사실 어렵 지 않 습 니 다. 몇 개의 간단 한 수학 등식 을 내 놓 을 수 있 잖 아 요. 나머지 복잡성 증명 은 생략 합 니 다.