KMP 알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다
𝑂(𝑁𝑀)
의 시간 복잡도를 가진다시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미
문자열 A | 'ABCDEFG' |
---|---|
문자열 B | 'EF' |
𝑂(𝑁𝑀)
의 시간 복잡도로 상당히 비효율적이다𝑂(𝑁 + 𝑀)
의 시간 복잡도로 문제를 해결할 수 있다KMP 알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다
1) 접두사와 접미사
abacdab
라고 가정. 2) 테이블 만들기
j=0
,i=1
로 설정하고 테이블 만들기를 진행
i
는 한 칸씩 이동pattern[j]
와 pattern[i]
가 일치하는지 반복적으로 확인.
불일치하는 경우 j를 마지막으로 일치했던 순간까지의 인덱스로 이동해 다시 검사.
table[j – 1]
마지막으로 일치했던 순간은 table[j – 1]
으로 이동해서 검사했을 때에도 일치하지 않을 경우 무시 ➡️ 0
이러한 과정을 마지막 문자까지 반복
3) 문자열 매칭 진행
table[j – 1]
𝑂(𝑁 + 𝑀)
의 시간 복잡도를 가진다