Algorithm 공부 #27 - KMP(Knuth–morris–pratt)

Algorithm 공부 #27 - KMP알고리즘 ✏️ 단순 문자열 비교 알고리즘 말 그대로 단순히 for문을 돌리면서 문자열을 하나하나씩 비교하는 알고리즘 하지만 이렇게 돌리게 되면 두 문자열의 길이를 n과 m이라고 했을 때 시간복잡도가 O(n*m)이고 n과 m이 1,000,000이상만 넘어가도 많은 시간이 걸리게 되는 단점이 있음 먼저 긴 문자열을 parent(BCDEF)라 하고 찾을 문자열을 DE라고 하면 가장 먼저 찾을 문자열을 parent맨 앞에 위치시키고 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 정답 이런 식으로 비교를 하게 되면 짧은 문자열은 상관이 없지만 문자열이 길어질수록 시간이 오래 걸리게 됨 ✏️ KMP 알..
Algorithm/알고리즘 공부 일기 2024. 4. 19. 13:42
1
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/11   »
일 월 화 수 목 금 토
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
글 보관함