-
Q) 길이가 $N$ 이하인 두 문자열 $A$와 $B$가 있다. 이때 $A$가 $B$를 substring으로 가지는지 판별하여라.
나이브를 생각해보자. $A$와 $B$의 길이를 각각 $a$, $b$라고 할 때 $A$의 모든 점에서 시작해 길이가 $b$인 substring을 뽑고, 그것이 $B$와 같은지 확인하면 되므로 나이브의 시간복잡도는 $O(N^{2})$이 된다. KMP 알고리즘은 이 문제를 선형에 푸는 데 사용된다.
직관적인 최적화를 생각해보자. 눈으로 두 문자열을 비교한다고 생각할 때, 우리는 위의 나이브 알고리즘처럼 하나하나 비교하지 않는다. 대충 표현하자면 좀 많이 겹치는 것 같은 부분을 집중해서 비교한다고도 할 수 있다. 이를 알고리즘적으로 서술하는 것이 가능할까?
KMP 알고리즘의 작동 방식을 알아보자.
우선 B에 대해 "실패 함수" 라는 배열을 만든다. 실패 함수는 $fail[i] =$ $($$B[0:j+1]$이 $B[0:i+1]$의 substring이 되는 $i$ 미만의 최대 $j$$)$로 정의된다. 그러한 $j$가 존재하지 않는다면 $fail[i] = -1$이라 하자.
실패 함수를 어떻게 구할 수 있는지는 조금 뒤로 넘기고, 일단 실패 함수가 구해져 있다고 생각한 다음 다시 나이브 알고리즘을 돌려보자. 코드로는 다음과 같이 표현될 것이다. (OOB 같은 문제는 알아서 잘 해결한다고 치자)
for(int i=0;i<a;i++){ int tmp = 0; for(int j=i;j<i+b;j++){ if(A[i]==B[j]) tmp++; else break; } if(tmp==b) return true; } return false;이제 위 코드를 최적화해보자. $A[i:i+tmp]$가 $B[0:tmp]$와 같을 때, $tmp \not = b$였다고 해서 $i$를 $1$ 늘리기만 하고 $tmp$를 $0$으로 보낸 후 같은 과정을 다시 반복하는 것은 너무 비효율적인 것 같다.
여기서 한 가지 관찰이 가능하다. 만약 $A[i:i+tmp]$가 $B[0:tmp]$와 같다면, $A[i:i+tmp-1]$은 $B[0:tmp-1]$과 같다. 그렇다면 아래와 같은 알고리즘을 짜면 되지 않을까?
int j = 0; for(int i=0;i<a;i++){ if(A[i]==B[j]) j++; else j = 0; if(j==b) return true; } return false;그러나 이 알고리즘은 $A = abababc, B = ababc$에서 틀리게 된다. $abab$까지 비교한 다음, $abc$와 $ababc$를 비교하는 것과 같은 동작으로 넘어가기 때문이다. 우리는 여기서, 실패 함수의 쓰임새를 추론할 수 있다. 앞에서부터 비교하다가 같지 않는 문자가 나왔을 때, 바로 처음으로 회귀하는 것이 아닌 실패 함수가 나타내는 인덱스로 회귀하면 되는 것이다. 이를 토대로 코드를 짜보면 아래와 같다.
int j = 0; for(int i=1;i<a;i++){ while(j>0&&A[i]!=B[j]) j = fail[j-1]+1; if(A[i]==B[j]) j++; if(j==b) return true; } return false;
그렇다면 실패 함수는 어떻게 구할 수 있을까? 놀랍게도 같은 과정을 $B$ 자기 자신에 대해서 수행하면 된다.
fail[0] = -1; int j = 0; for(int i=1;i<b;i++){ while(j>0&&B[i]!=B[j]) j = fail[j-1]+1; if(B[i]==B[j]) j++; fail[i] = j-1; }
시간복잡도를 분석해보자. 실패 함수를 만드는 코드와 $A$에 $B$가 포함되는지 확인하는 코드의 구조가 같으므로, 후자의 시간복잡도만 분석하면 될 것이다. 코드의 형태는 for문 안에 while문이 들어간 형태로, while문을 제외한 나머지 부분은 $O(a)$일 것이다. while문의 실행 횟수를 따져보면, 우선 while문이 한 번 돌아가면 j는 항상 줄어든다. 그리고, for문이 한 번 도는 동안 j는 최대 한 번 늘어난다. j는 0 아래로 줄어들지 않으므로, j가 줄어드는 횟수는 j가 늘어나는 횟수보다 많을 수 없다. 따라서, while문이 소비하는 연산 횟수는 $O(a)$라는 것을 알 수 있다. 즉 $A$에 $B$가 포함되는지 확인하는 총 시간복잡도는 $O(a)$임을 알 수 있다. 같은 원리로, 실패 함수를 만드는 시간복잡도는 $O(b)$가 된다. 따라서 총 시간복잡도는 $O(a+b)$이고, 만약 $b>a$이면 애초에 $A$가 $B$를 포함할 수 없으므로 바로 알고리즘을 끝낸다고 하면 시간복잡도는 $O(a)$가 된다.