ps:kmp_알고리즘
KMP 알고리즘
- 기본적으로 KMP 알고리즘은 문자열 매칭을 선형시간에 해결해주는 알고리즘이다.
- KMP 알고리즘에서는 문자열 매칭을 위해서 fail 함수라는 것을 정의해서, 패턴 P에 대한 fail함수의 table을 구하고, 이를 이용해서 스트링 S에서 P의 모든 occurrence를 효율적으로 찾는다.
- fail함수를 pi배열이라고도 부른다
- 문자열 검색은 실용적으로 너무나 흔하고 중요한 기능이므로, 이 기능이 가장 중요하게 생각되는 것은 당연하다. 그래서 KMP 알고리즘에 대한 보통의 설명은 다음 순서로 진행되는거 같다,
- 문자열을 빠르게 매칭하기 위해서는 이러이러한 불필요한 과정을 줄일수 있으면 좋을거 같아 ⇒ 이런 형태의 테이블이 있다고 생각하자. 그러면 그 테이블을 갖고서 이런 방법으로 매칭하면 불필요한 과정을 줄여서 O(m+n)에 매칭이 될거 같아 ⇒ 이 테이블을 만드는 방법도 매칭할때의 알고리즘을 비슷하게 적용하면 O(m)에 만들수 있을거 같아 ⇒ 오 이렇게 해서 O(m+n) 매칭이 되는구나
- 하지만, PS쪽에서는 문자열 매칭 자체보다는 fail 함수의 특징을 이용해서 활용하는 능력이 더 중요해보인다..
- 문자열 매칭으로는 여기에서 뭔가 응용/변형을 해서 문제를 만들기가 좀 어려운거 같다.
- 다시 말하면, fail 테이블을 구하는 과정보다도 fail 테이블을 O(n)에 구해 놓은 상태에서, 이걸 어떻게 활용해서 문제에서 원하는 값을 구할것인가가 더 중요한 느낌이긴 하다.
- 이 관점으로는 문자열 매칭문제도 이렇게 바꿔서 해결할수 있다.
- (n=len(P)라고 할때) P#S 에 대해서 fail 함수를 구한 다음에, fail[i] == n이 되는 i를 모두 찾으면 된다. S[i-n*2:i-n] == P 이다.
- 그럼 진짜로 fail 함수를 활용해서 어떤 문제를 풀수 있을지는 문자열쪽에서 설명.
구현
- 알고리즘이 매우 컴팩트하게 구현되는 편이라서, 사람들마다 코드 차이가 별로 없을것 같다
- failure table을 만드는 함수와, failure table를 이용해서 매칭을 하는 함수를 분리해서 만들었다
- 코드
벤치마크
ps/kmp_알고리즘.txt · 마지막으로 수정됨: 2022/12/21 12:51 저자 teferi
토론