종문북 p650 KMP 질문드립니다.

  • 7041701
    7041701

    p650에 나오는 코드중 질문을 드릴까합니다.

    kmpSearch는 짚더미에서 바늘과 일치하는 모든 시작점을 반환하는데

    if(matched==m) ret.push_back(begin)에서
    시작위치를 넣고나서

    match=0, begin++이라는 갱신을 해주어야 하지 않나요??


    9년 전
1개의 댓글이 있습니다.
  • songmw725
    songmw725

    ret에 begin 값을 집어넣고 while문을 다시 돌면
    if( matched < m ...) <-- 이 조건에 의해 밑의 else 문으로 가게 됩니다.
    그리고 나서 begin과 matched값이 다시 세팅 되는거죠.

    이때 match = 0, begin++ 이렇게 세팅 되는것이 아닙니다.
    aabaab가 찾는 문자열이라고 생각해보시면 쉽게 이해가 되실겁니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.