KMP : 문자열 검색 알고리즘
문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한 것입니다. 본문에서 89개의 "테이프"를 찾았다고 순식간에 알려주네요. 이렇게 텍스트내(본문)에서 특정 문자열, 패턴("테이프")를 찾는 것을 문자열 검색이라고 부릅니다. 이 문자열 검색은 어떤 방식으로 구현되는걸까요? 가장 단순한 문자열 검색 먼저 가장 단순한 방법의 문자열 검색을 생각해봅시다. 텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾아봅시다. 패턴 "ABC"를 한자리씩 옮기면서 같은지 비교합니다. 같아? A B C A B A B C D E A B C ->같아! ..
알고리즘
2016. 1. 17. 01:11
최근에 달린 댓글
- Total
- Today
- Yesterday