문자열 탐색1 KMP 알고리즘 문자열에 조금 약한 편이라서 한동안 문자열과 관련된 알고리즘에 대해서 공부해보려고 합니다. 첫 번째로는 KMP(Knuth-Morris-Pratt) 알고리즘입니다. KMP는 문자열을 탐색하기 위한 것인데, 어떤 문자열 A와 B가 있을때, 문자열 A에서 B를 포함하고 있는지 탐색하는 것입니다. "This is a pen. I have a pen." 이라는 문장에서 have라는 단어를 찾는다고 한다면, 사람이야 그저 눈으로 훑어보고 바로 어디 있는지 찾을 수 있지만, 컴퓨터로 단순하게 찾는다면 이중for문으로 완전탐색을 통해서 찾을 수 있습니다. 완전탐색으로 찾는다면, 시간복잡도는 O(NM)이며, 문자열의 길이가 길어질수록 급격하게 걸리는 시간이 증가해서 시간초과가 발생하기 십상입니다. 그러나, KMP 알고리.. 2020. 11. 25. 이전 1 다음
