자료
-
KMP 알고리즘자료 2024. 7. 15. 12:17
Q) 길이가 $N$ 이하인 두 문자열 $A$와 $B$가 있다. 이때 $A$가 $B$를 substring으로 가지는지 판별하여라.나이브를 생각해보자. $A$와 $B$의 길이를 각각 $a$, $b$라고 할 때 $A$의 모든 점에서 시작해 길이가 $b$인 substring을 뽑고, 그것이 $B$와 같은지 확인하면 되므로 나이브의 시간복잡도는 $O(N^{2})$이 된다. KMP 알고리즘은 이 문제를 선형에 푸는 데 사용된다. 직관적인 최적화를 생각해보자. 눈으로 두 문자열을 비교한다고 생각할 때, 우리는 위의 나이브 알고리즘처럼 하나하나 비교하지 않는다. 대충 표현하자면 좀 많이 겹치는 것 같은 부분을 집중해서 비교한다고도 할 수 있다. 이를 알고리즘적으로 서술하는 것이 가능할까?KMP 알고리즘의 작동 방식을 ..