코딩못하는사람

KMP 알고리즘이란? 우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다. 알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는 N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다. 하지만 KMP알고리즘은 O(N+M)정도로 줄여준다 KMP알고리즘에는 두가지 함수가 필요하다 전처리 테이블 KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다 접두사와 접미사 같을때의 최대길이를 저장해주는 것이다 코드로 구현하면 다음과 같다. KMP 함수구현 이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다 그림으로 보면 3번 인덱..