접두사
-
[Algorithm] - 문자열 알고리즘 (KMP 알고리즘)Algorithm/Algorithm 2022. 9. 5. 14:07
문자열 탐색 문자열을 검색하는 상황은 많은 상황에서 쓰입니다. 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 Ctrl+F 를 눌러서 검색 시 사용될 수 있습니다. 본문에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니다. 문자열 검색이라고 생각하면 됩니다. 1. 일반적인 생각 ( Brute-Force ) 본문 문자열의 길이를 M, 패턴의 길이를 N이라 가정 시간 복잡도 : O(NM) 2. KMP 알고리즘(Knuth Morris Partt Algorithm) 접두사와 접미사가 같은 부분부터 다시 매칭하면 된다라는 아이디어 시간 복잡도 : O( N+M ) 1) 접두사( Prefix ) banana -> b / ba / ban / bana ..