아래 코드는 KMP알고리즘에서의 Preprocessing 과정입니다.
책의 설명에 '현재 matched 글자가 일치했다면,
pi[matched-1]은 항상 계산된 뒤임을 증명할 수 있기 때문입니다'
라는 문장이 있는데요, 이게 이해가 가지 않습니다 ㅠㅠ
어떻게 하면 증명할 수 있을까요?
(알고리즘 문제 해결 전략 2권 - 653페이지와 95% 동일한 코드입니다.)
// 바늘 문자열 N을 입력받아서, N의 모든 접두사에 대해서// 그것의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 // 담은 벡터를 반환한다.vector<int>getPartialMatch3(conststring&N){vector<int>pi(N.size(),0);intbegin=1,matched=0;while(begin+matched<N.size()){if(N[begin]==N[begin+matched]){matched++;pi[begin+matched-1]=matched;}else{if(matched==0)begin++;else{begin+=matched-pi[matched-1];// !!matched=pi[matched-1];}}}returnpi;}
Signin
아래 코드는 KMP알고리즘에서의 Preprocessing 과정입니다.
책의 설명에 '현재 matched 글자가 일치했다면,
pi[matched-1]은 항상 계산된 뒤임을 증명할 수 있기 때문입니다'
라는 문장이 있는데요, 이게 이해가 가지 않습니다 ㅠㅠ
어떻게 하면 증명할 수 있을까요?
(알고리즘 문제 해결 전략 2권 - 653페이지와 95% 동일한 코드입니다.)
10년 전