Knuth-Morris-Pratt 문자열 매칭에서 이해가 안되는 부분이 있어요;
글쓴이: newpolaris / 작성시간: 월, 2010/04/12 - 6:18오후
for(int idx = 1; idx < _t_L; idx++)
{
int i = fail[idx-1];
while( *(ptr + idx) != *(ptr + i +1) && i>=0)
{
i = fail[i];
}
if ( *(ptr + idx) == *(ptr + i +1)) fail[idx] = i + 1;
else fail[idx] = -1;
}이 책에 나와있는 failure function 인데요,
(fundamentals of data structures in c++ 입니다.)
i = fail[i];
의 동작을 살펴봤는데요, while 문 안에서 단순히,
i값을 바꿔가면서 -1을 향해 가는 것으로 밖에 생각이 안됩니다.
그러면 차라리 fail[idx] = -1; i = -1;
이렇게 처음부터 시작하라고 지정해 놓는게 좋지 않은건지;
머 제가 생각 못한 다른 기능이 있는건지 궁금합니다.
Forums: