매트릭스 황소 KMP 알고리즘

다음으로 이동:http://www.matrix67.com/blog/archives/tag/kmp%E7%AE%97%E6%B3%95
기관실 이 곧 문 을 닫 거나 MM 과 데 이 트 를 급히 하려 면 여섯 번 째 자연 구간 으로 뛰 어 내 려 보 세 요.    우리 가 여기 서 말 하 는 KMP 는 영 화 를 방영 하 는 것 이 아니 라 알고리즘 이다.KMP 알고리즘 은 문자열 을 처리 하 는 데 사 용 됩 니 다.다시 말 하면 두 개의 문자열 을 드 리 겠 습 니 다.B 문자열 이 A 문자열 의 하위 문자열 인지(A 문자열 이 B 문자열 을 포함 하 는 지)대답 해 야 합 니 다.예 를 들 어 문자열 A="I'm matrix 67",문자열 B="matrix",우 리 는 B 가 A 의 하위 문자열 이 라 고 말한다.당신 은 당신 의 MM 에 게 완곡 하 게 물 어 볼 수 있 습 니 다."만약 당신 이 좋아 하 는 사람 에 게 고백 하려 고 한다 면,나의 이름 은 당신 의 고백 말의 하위 꼬치 입 니까?"    이러한 문 제 를 해결 하 는 방법 은 보통 A 열의 어떤 위치 부터 B 와 일치 하 는 지 를 매 거 진 다음 에 일치 하 는 지 검증 하 는 것 입 니 다.만약 A 열 길이 가 n 이 고 B 열 길이 가 m 라면 이런 방법의 복잡 도 는 O(mn)이다.복잡 도가 mn 에 이 르 지 못 할 때 가 많 지만(검증 할 때 첫 글자 한두 개 만 보면 일치 하지 않 음 을 발견 합 니 다)우 리 는 많은'최 악의 상황'이 있 습 니 다.우리 가 소개 할 것 은 최 악의 상황 에서 O(n)의 알고리즘(여기 서 m<=n 을 가정 합 니 다),즉 전설의 KMP 알고리즘 입 니 다.    KMP 라 는 이 유 는 이 알고리즘 이 Knuth,Morris,Pratt 세 개 에서 제 기 된 것 으로 이 세 사람의 이름 의 첫 번 째 자 모 를 지 었 기 때문이다.이때,아마도 당신 은 갑자기 AVL 나무 가 왜 AVL 이 라 고 부 르 는 지,아니면 Bellman-ford 가 왜 중간 에 한 줄 이 아니 라 는 것 을 알 게 되 었 을 것 입 니 다.어떤 때 는 한 물건 을 칠 팔 명 이 연구 한 적 이 있 는데,그것 은 어떻게 명명 합 니까?보통 이 물건 은'3x+1 문제'와 같은 사람들의 이름 을 아예 쓰 지 않 는 다.멀리 갔 어.    개인 적 으로 KMP 는 인터넷 에서 많은 자 료 를 찾 을 수 있 기 때문에 가장 말 할 필요 가 없 는 것 이 라 고 생각한다.그러나 인터넷 의 설법 은 기본적으로'이동(shift)','Next 함수'등 개념 과 관련 되 는데 이것 은 오해 하기 쉽다(적어도 1 년 반 전에 나 는 이 자 료 를 보고 KMP 를 배 울 때 잘 알 지 못 했다).여기 서 KMP 알고리즘 을 설명 하 는 방법 을 바 꾸 겠 습 니 다.    만약 에 A="abababaababacb",B="ababacb",KMP 가 어떻게 일 하 는 지 봅 시다.우 리 는 두 개의 지침 i 와 j 로 각각 A[i-j+1.i]와 B[1.j]가 완전히 같다 고 표시 했다.즉,i 는 계속 증가 하고 i 의 증가 에 따라 j 는 상응 하 게 변화 하 며 j 는 A[i]로 끝 나 는 길 이 를 j 로 하 는 문자열 이 B 문자열 의 앞 j 문자(j 는 당연히 클 수록 좋다)와 일치 하 는 것 을 만족 시 키 므 로 지금 은 A[i+1]과 B[j+1]의 관 계 를 검증 해 야 한다.A[i+1]=B[j+1]시 i 와 j 가 각각 1 을 추가 합 니 다.언제 j=m 가 되 었 습 니까?우 리 는 B 가 A 의 하위 꼬치(B 꼬치 가 이미 완성 되 었 습 니 다)라 고 말 하고 이때 의 i 값 에 따라 일치 하 는 위 치 를 계산 할 수 있 습 니 다.A[i+1]<>B[j+1]에서 KMP 의 전략 은 j 의 위 치 를 조정 하 는 것(j 값 을 줄 이 는 것)입 니 다.i=j=5 시의 상황 을 살 펴 보 자.    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B = a b a b a c b     j = 1 2 3 4 5 6 7     이때 A[6]<B[6].이것 은 이때 j 가 5 와 같 을 수 없다 는 것 을 나타 낸다.우 리 는 j 를 그것 보다 작은 값 j 로 바 꿔 야 한다.제 이 가 얼마 일 까요?곰 곰 이 생각해 보 니 j'는 B[1.j]의 머리 j'자모 와 끝 j'자 모 를 완전히 같 게 해 야 한 다 는 것 을 알 게 되 었 다.이 제 이 는 당연히 크 면 클 수록 좋다.여기 서 B[1.5]="ababa"는 첫 세 글자 와 끝 세 글자 가 모두"aba"입 니 다.그리고 새로운 j 가 3 일 때 A[6]는 마침 B[4]와 같다.그래서 i 는 6 이 되 었 고 j 는 4 가 되 었 다.    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B =     a b a b a c b     j =     1 2 3 4 5 6 7     위의 이 예 에서 우 리 는 새로운 j 가 얼마나 취 할 수 있 는 지 i 와 상 관 없 이 B 꼬치 와 만 관련 이 있다 는 것 을 알 수 있다.우 리 는 이러한 배열 P[j]를 미리 처리 할 수 있 습 니 다.B 배열 의 j 번 째 자모 와 일치 하고 j+1 번 째 자모 가 일치 하지 않 을 때 새로운 j 는 최대 얼마 입 니까?P[j]는 모든 만족 B[1.P[j]=B[j-P[j]+1.j]의 최대 치 일 것 이다.    그 후에 A[7]=B[5],i 와 j 는 각각 1 이 증가 했다.이때,또 A[i+1]<>B[j+1]의 상황 이 나 타 났 다.    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B =     a b a b a c b     j =     1 2 3 4 5 6 7     P[5]=3 으로 인해 새로운 j=3:    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B =         a b a b a c b     j =         1 2 3 4 5 6 7     이때,새로운 j=3 은 여전히 A[i+1]=B[j+1]를 만족 시 키 지 못 한다.이때 우 리 는 j 값 을 다시 줄 이 고 j 를 다시 P[3]로 업데이트 한다.    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B =             a b a b a c b     j =             1 2 3 4 5 6 7     지금 i 인지 7 인지 j 는 1 이 되 었 다.이때 A[8]는 B[j+1]와 같 지 않 았 다.이렇게 하면 j 는 반드시 P[1],즉 0 으로 줄 여야 한다.    i = 1 2 3 4 5 6 7 8 9 ……     A = a b a b a b a a b a b …     B =               a b a b a c b     j =             0 1 2 3 4 5 6 7     마침내 A[8]=B[1],i 는 8,j 는 1 로 바 뀌 었 다.사실 j 가 0 이 되 어도 A[i+1]=B[j+1](예 를 들 어 A[8]='d'시)를 만족 시 키 지 못 할 수도 있다.따라서 정확 한 말 은 j=0 이 되면 우 리 는 i 값 을 증가 하지만 j 가 A[i]=B[1]가 나타 날 때 까지 무시 한 다 는 것 이다.    이 과정의 코드 는 매우 짧다.    마지막 j:=P[j]는 프로그램 을 계속 하기 위해 서 입 니 다.여러 곳 에서 일치 하 는 것 을 찾 을 수 있 기 때 문 입 니 다.    이 프로그램 은 생각 보다 간단 할 수도 있 습 니 다.i 값 이 계속 증가 하기 때문에 코드 는 for 순환 을 사용 합 니 다.따라서 이 코드 는 문자열 A 를 스 캔 하고 B 와 일치 하 는 위 치 를 업데이트 할 수 있 습 니 다.    지금 우 리 는 두 가지 중요 한 문 제 를 남 겼 다.하 나 는 왜 이 프로그램 이 선형 입 니까?2.P 배열 을 어떻게 빨리 예비 처리 합 니까?    왜 이 프로그램 은 O(n)입 니까?사실 주요 논란 은 while 순환 으로 인해 집행 횟수 가 불확실 하 다 는 점 이다.우 리 는 시간 복잡 도의 할당 분석 에서 의 주요 전략 을 사용 할 것 이다.쉽게 말 하면 특정한 변수 나 함수 값 의 변 화 를 관찰 함으로써 분산 되 고 난잡 하 며 불규칙 한 집행 횟수 를 누적 하 는 것 이다.KMP 의 시간 복잡 도 분석 은 노점 분석의 전형 이 라 고 할 수 있다.우 리 는 상술 한 프로그램의 j 값 부터 시작한다.매번 while 순환 을 실행 할 때마다 j 를 줄 일 수 있 지만 마이너스 로 줄 일 수 없 으 며,다른 j 값 을 바 꾸 는 곳 은 다섯 번 째 줄 에 불과 합 니 다.이 줄 을 실행 할 때마다 j 는 1 만 추가 할 수 있 습 니 다.그래서 전체 과정 에서 j 는 최대 n 개 1 을 추가 했다.따라서 j 는 최대 n 번 만 줄 일 수 있 는 기회(j 값 이 줄 어 든 횟수 는 당연히 n 을 초과 할 수 없다.왜냐하면 j 는 영원히 부정 정수 이기 때문이다).while 순환 은 총 n 회 까지 실 행 된 것 으로 알려 졌 다.노점 분석 에 따 르 면 매번 for 순환 에 평평 하 게 펼 친 후 한 번 for 순환 의 복잡 도 는 O(1)이다.전체 과정 은 분명히 O(n)의 것 이다.이러한 분석 은 뒤의 P 배열 의 예비 처리 과정 에 도 효과 가 있 고 예비 처리 과정의 복잡 도 는 O(m)이다.    예비 처 리 는 P 의 정의 에 따라 O(m^2),심지어 O(m^3)로 쓸 필요 가 없습니다.우 리 는 P[1],P[2],...,P[j-1]의 값 을 통 해 P[j]의 값 을 얻 을 수 있다.아까 B="ababacb"에 대해 만약 에 우리 가 P[1],P[2],P[3]와 P[4]를 구 했다 면 우리 가 P[5]와 P[6]를 어떻게 구 해 야 하 는 지 보 자.P[4]=2,그러면 P[5]는 분명히 P[4]+1 과 같다.P[4]에서 알 수 있 듯 이 B[1,2]는 B[3,4]와 같 고 지금 은 B[3]=B[5]가 있 기 때문에 P[5]는 P[4]뒤에 한 문 자 를 더 해서 얻 을 수 있다.P[6]도 P[5]+1 인가요?분명히 그렇지 않 습 니 다.B[P[5]+1]<>B[6]때 문 입 니 다.그럼,우 리 는 한 걸음 물 러 서 는 것 을 고려 해 야 한다.우 리 는 P[6]가 P[5]의 상황 에 포 함 된 하위 문자열 을 얻 을 수 있 는 지,즉 P[6]=P[5]]+1 여 부 를 고려 합 니 다.여기 서 이해 가 안 되면 자세히 볼 수 있다.        1 2 3 4 5 6 7     B = a b a b a c b     P = 0 0 1 2 3 ?     P[5]=3 은 B[1.3]와 B[3.5]가 모두"aba"이기 때문이다.그리고 P[3]=1 은 우리 에 게 B[1],B[3]와 B[5]가 모두'a'라 고 알려 주 었 다.P[6]를 P[5]로 얻 을 수 없 으 니 P[3]로 얻 을 수 있 을 지도 모른다.분명히 P[6]도 P[3]를 통 해 얻 을 수 없다.왜냐하면 B[2]<>B[6]때문이다.사실 이렇게 P[1]까지 미 루 면 안 돼 요.마지막 으로 우 리 는 P[6]=0 을 얻 었 어 요.    왜 이 예비 처리 과정 이 앞의 KMP 메 인 프로그램 과 이렇게 비슷 합 니까?사실 KMP 의 사전 처리 자체 가 B 열'자기 일치'의 과정 이다.그것 의 코드 는 위의 코드 와 비슷 하 다.    마지막 으로 한 가지 보충:KMP 알고리즘 은 B 열 만 미리 처리 하기 때문에 이러한 알고리즘 은 이러한 문제 에 적합 합 니 다.B 열 과 다른 A 열 을 지정 하고 B 가 어떤 A 열 이 냐 고 물 습 니 다.    꼬치 매 칭 은 매우 연구 가치 가 있 는 문제 이다.사실 우 리 는 접미사 트 리,자동 동기 등 여러 가지 방법 도 있 습 니 다.이런 알고리즘 들 은 모두 예비 처 리 를 교묘 하 게 활용 하여 선형 시간 에 문자열 의 매 칭 을 해결 할 수 있 습 니 다.우리 나중에 얘 기 하 자.