달력

122018  이전 다음

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  
  •  
  •  

'String matching'에 해당되는 글 1건

  1. 2010.11.16 KMP String matching (3)
문자열 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
틀렸는데도 아무 댓글이 없다는게 쓸쓸하네요......ㅠ,.ㅠ ㅋㅋ


소스는 아래와 같습니다.

Posted by 오산돌구