Sangmun

https://www.youtube.com/watch?v=UcjK_k5PLHI # Python3 program for KMP Algorithm def KMPSearch(pat, txt): M = len(pat) N = len(txt) # create lps[] that will hold the longest prefix suffix # values for pattern lps = [0] * M j = 0 # index for pat[] # Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps) i = 0 # index for txt[] while (N - i) >= (M - j): if pat[j] == txt[i]: i +..

Rabin Karp 알고리즘은 문자열 매칭 알고리즘이며 문자열 매칭을 O(n)의 시간안에 수행하게 해주는 알고리즘이다. 문자열 매칭은 다음과 같은 사례가 있다. 우리가 찾고자 하는 문자열을 target이라고 하고 대상이 되는 문자열을 S라고 했을때 아래 그림처럼 문자열을 하나씩 옮겨가면서 BruteForce 방식으로 찾게되면 len(target)*len(S)의 time complexity가 소요되게 된다. 즉 O(n**2)이라고 봐도 무방한것이다. Rabin karp 알고리즘은 이러한 brute force방식의 문제점을 해결하여 O(n) time complexity로 문자열을 찾는 알고리즘이다. 핵심아이디어는 다음과 같다. * brute force방식으로 문자열의 자리를 하나씩 옮겨가며 비교하지 말고 해..