[Algorithm] KMP 알고리즘 (문자열 매칭 알고리즘)

문자열 알고리즘이란 어떤 문자열에서 원하는 패턴을 찾는 알고리즘이다. 문자열의 부분 문자열과 패턴을 비교하면서 패턴의 존재 여부를 알 수 있다. 예를 들어서 "banana"에서 "ana"라는 패턴을 찾고자한다면 "banana", "banana" 이렇게 총 두 개가 존재함을 알 수 있다. 그러나 모든 부분 문자열과 패턴을 비교한다면 엄청난 시간이 걸릴 것이다. 그래서 KMP 알고리즘을 사용하면 패턴 비교시간을 줄일 수 있다. KMP 알고리즘의 필요성 굉장히 긴 문자열이 존재하고 이 문자열에서 "abcac"라는 문자열을 찾고 싶다고하자. 패턴을 찾는 와중에 위와 같은 상황이 발생했다고 하자. abca까지는 맞았으나 그 다음 문자열에서 찾고있는 패턴이 아님을 알아냈다. 그럴 경우 패턴을 한 칸 옆으로 옮겨서 ..

2022.12.18