알고리즘 #String #Algorithm #KMP
-
[알고리즘 소개] String Algorithm - KMP algorithmComputer - Problem Solving/Algorithm 2022. 9. 28. 22:52
문자열 알고리즘의 대표적인 알고리즘 되시겠다. Knuth–Morris–Pratt 세 명의 첫 글자를 따서 KMP라고 불린다. 어디에 쓰는 알고리즘인고? 우리가 네이버나 구글에 검색어를 치면 검색어가 포함된 게시글을 바로바로 보여준다. 세세한 것은 다르겠다만, “banana”라는 글자를 치면 바로 “banana” 키워드가 있는 게시물을 보여준다. 게시물 하나하나에 banana가 들어가있는지 검색해줄 뿐만 아니라 banana 단어에 bold로 표시하면서 게시물에 banana가 있음을 우리에게 확인시켜주고 있다. 이를 빨리 해결하는 데 쓰는 알고리즘이 바로 KMP algorithm 되시겠다. Brute Force 알고리즘 – O(NM) S1 = “I love apple and banana” S2 = “bana..