ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • KMP String matching
    개발하면서/Algorithm,Data Structure 2010.11.16 01:21
    문자열 S, P가있고, S에서 P를 검색한다고 할때, 가장 기초적인건 아래와 같이 검색을 합니다.




    비효율적인부분이 있습니다.  그래서 Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘을 지금 설명하려고 합니다.

    제가 이해한것을 풀어쓰는거라 잘못 이해한 것이 있을 수도 있습니다.
    그럴때는 말씀해주시면 감사하겠습니다.

    KMP는 패턴을 만들어서 검사에 실패했을때 다음 검사에서 불필요한 부분을 생략하는데 있습니다.
    위 그림은 검사에 실패했을때 P를 오른쪽으로 한칸 이동하지만 KMP는 안해도 되는부분은 과감히 건너뜁니다.

    KMP는 크게 나눠보면 찾고자하는 문자열에 패턴을 구하고 그 패턴을 이용해서 검사를 하는 것입니다.

    문자열 페턴 구하는것을 설명하기에 앞서 suffix, prefix에 대해 알아봅시다.

    문자열 abcdabc에 대한 suffix, prefix는

       prefix suffix
     1  a  c
     2  ab  bc
     3  abc  abc
     4  abcd  dabc
     5  abcda  cdabc
     6  abcdab  bcdabc
     7  abcdabc  abcdabc




    3번 열을 보면 'abc', 'abc'같죠?  [ 마지막 전체 비교는 필요없는거죠....허허]
    패턴을 찾는건 suffix와 prefix가 같은 부분을 찾는다고 할수 있습니다.

    [a는 할필요가 없겠죠?]
    ab, abc, abcd, abcda, abcdab, abcdabc에 대한 suffix, prefix가 같으면서 가장 긴~부분을 찾는 것이죠.


    index 5, 문자 'b'를 예로 들면,
    abcda까지 문자열 매칭이 됐는데, b에서 틀릴경우 1번째 문자로 이동하라는 얘기입니다.

    1
     a
     a
    2
     ab
     da
    3
     abc
     cda
    4
     abcd
     bcda
    5
     abcda  abcda

    첫번째문자 'a'와 마지막 문자 'a'가 같으니 이동해도 문제없겠죠?


    6번째 문자 C의 경우, 매칭된 문자열은 abcab이고   최대 prefix, suffix는   ab이므로  2가 들어간것이죠~ : )
    c,6이 실패했을때 진행방향이 틀렸네요;; d,3이 아니라 c,2로 이동하는게 맞습니다. 2010/12/01
    틀렸는데도 아무 댓글이 없다는게 쓸쓸하네요......ㅠ,.ㅠ ㅋㅋ


    소스는 아래와 같습니다.

    댓글 3

Designed by Tistory.