탐색 대상 문자열의 길이가 $N$이고, 쿼리 문자열의 길이가 $M$일 때, naive하게 전수조사 하는 경우 시간복잡도는 $O((N-M+1)M)$입니다. 이는 $M$이 1이거나, $N$과 같은 값을 가지는 등의 극단적인 경우가 아니면 비효율적입니다. 최악의 경우 $M$이 $N/2$ 근처의 값인 경우 시간복잡도는 $O(N^2)$이 됩니다.
    예를 들어, 문자열 탐색 문제의 경우 $N$, $M$이 $10^6$의 최댓값을 갖는데, 이 때 문자열 탐색 알고리즘을 naive하게 구현하면 $N$이 $10^6$이고 $M$이 대략 $5\times10^5$일 때가 최악의 경우이므로 시간 초과가 뜹니다. 여담으로 이 문제가 bronze 2인 것은 일부 언어의 경우 라이브러리를 쓰면 시간 내로 풀리기 때문입니다. java의 경우 KMP를 직접 구현해야 시간초과가 나지 않습니다.
    그럼 KMP가 뭔지 알아보겠습니다.

1. KMP 알고리즘의 개요

    KMP 알고리즘의 핵심은 "pi 배열"에 담긴 정보를 바탕으로 불필요한 반복을 줄이는 것입니다. 결과만 얘기하면, KMP 알고리즘의 시간복잡도는 $O(N+M)$입니다. 이는 pi 배열 구하는 시간 $M$, 전체 탐색 시간 $N$을 더한 것입니다. 이제 KMP 알고리즘을 두 단계로 분석해서, 어떻게 시간복잡도를 선형으로 만들 수 있는지 알아보겠습니다.

2. pi 배열 구하기

    pi 배열 구하는 과정에서 필요한 배경지식이 있는데, 바로 문자열의 prefix와 suffix입니다. 우리말로 해석하면 접두사, 접미사입니다. 이 prefix와 suffix의 정의를 알아보겠습니다.

Prefix, Suffix

    "AABAACDAABAAE"라는 문자열로 예시를 들어보겠습니다. prefix는 다음 규칙을 따릅니다.

A
AA
AAB
AABA
AABAA
... (생략) ...
AABAACDAABAAE (not proper prefix)

    즉, prefix는 index 0부터 시작한 부분문자열입니다. 이 때, prefix 중에서 AABAACDAABAAE는 원래 문자열과 같은데, 이것만 제외한 prefix들을 proper prefix라고 합니다. pi 배열을 구할 때는 proper prefix를 이용할 것입니다.

    같은 문자열에 대해 suffix는 문자열의 끝에서부터 부분문자열을 표현합니다. 마찬가지로 자기 자신을 제외한 suffix는 proper suffix입니다.

E
AE
AAE
BAAE
ABAAE
... (생략) ...
AABAACDAABAAE (not proper suffix)

proper prefix와 suffix가 같은 최대 길이

    pi 배열의 값은 문자열의 인덱스 0부터 i까지 substring에 대해 proper prefix와 suffix가 같은 최대 길이입니다. 다시 표현하면, prefix 이면서 동시에 suffix인 부분 문자열의 최대 길이입니다. 글로 표현하면 어렵지만, 규칙을 천천히 따라가보면 pi 배열이 무엇인지 금방 파악할 수 있습니다.
    위에서 예시로 들었던 "AABAACDAABAAE"로 시작해보겠습니다. 일단, pi[0]는 0으로 초기화합니다. 이는 길이가 1인 문자열은 proper prefix가 없기 때문입니다. 아래 표에서 굵게 표시한 부분이 proper prefix와 suffix가 같은 부분 문자열 중 최대 길이를 표시한 것입니다.

pi 배열을 $O(M)$으로 구하기

    이제 pi 배열을 작성하는 규칙을 알았으니, 이것을 $O(M)$에 구하는 방법을 찾아야합니다. 이것 또한 naive하게 구현하면 각 부분문자열을 전수조사 하게 되는 셈이므로, $O(M^2)$이 됩니다. 빠르게 구하려면 이전에 얻었던 정보들을 이용해야 합니다. 이 정보를 이용할 변수를 x라고 두겠습니다. x는 매치된 최대 길이가 됩니다. x와 i를 설정하는 규칙은 아래와 같습니다.

x는 0으로 초기화하고, i는 1로 초기화한다.
N[x]와 N[i]가 같으면(match) x, i를 1 증가시킨다.
N[x]와 N[i]가 다르면(dismatch)

• x가 0이면 i를 1 증가시킨다.
• x가 0이 아니면 x=pi[x-1] 이다.

    일치하면 인덱스(i)를 1만큼 증가시키고, 매치 길이를 의미하는 x도 1만큼 증가시킵니다. 이는 이전에 얻었던 정보를 이용한 것이므로 당연합니다. 그런데 dismatch 상황에서는 왜 x를 pi[x-1]로 설정해야할까요? 위의 표에서 index가 12일 때 pi[12]=0을 결정하는 과정을 살펴보겠습니다.
    먼저, 문자열 끝 인덱스는 12이므로 i는 12이고, x는 이전에 매치된 최대 길이가 저장되므로 x=pi[12-1]=5일 것입니다.

    그런데, N[x]='C'와 N[i]='E'는 일치하지 않습니다. 그럼 N[i]를 다시 어디서부터 비교해야할까요? x를 단순히 1만큼 감소시켜가며 비교해버리면 성능 이득이 없을 것입니다.
    이 질문에 대한 답이 pi[x-1]입니다. pi[x-1]은 부분배열이 x-1일 때 proper prefix=suffix인 최대 길이입니다. 위에서 pi[5-1]=pi[4]=2 이므로, pi[x-1]=2 입니다. 이 과정을 끝까지 반복하면 아래 표와 같이 나타납니다.

    $x_{0}={pi}[i-1]=N_{0}$ 이라는 것은 $i$ 이전의 $N_{0}$개와 $x_{0}$이전의 $N_{0}$개가 같다는 것입니다. 불일치한 경우에 이 $N_{0}$개에 대해 i-x 대응 관계를 반복해보면, 동일한 관계에 의해 ${pi}[x_{0}-1]=N*{1}$ 개에 대해서는 $i$ 이전의 $N*{1}$개와 $x_{1}$ 이전의 $N_{1}$개는 같다는 결론을 얻을 수 있습니다. 이런 사고의 흐름이 결국 문자열 탐색에서도 동일하게 나타납니다.
    이 과정을 getPi 함수로 나타내면 아래와 같습니다. String을 입력으로 받아 int 배열을 반환합니다.

public int[] getPi(String P) {
  int[] pi = new int[P.length()];
  int x = 0, i = 1;
  while (i < pi.length) {
      if (P.charAt(x) == P.charAt(i)) { // match
          pi[i++] = ++x;
      } else {  // dismatch
          if (x != 0) {
              x = pi[x - 1];
          } else {
              pi[i++] = 0;
          }
      }
  }
  return pi;
}

3. 문자열 탐색

탐색 과정의 그림

    아래 예시를 보면 pi 배열이 주는 정보로 어떻게 시간복잡도가 줄어드는지 알 수 있습니다. 핵심은 mismatch가 발생한 순간 pi정보를 바탕으로 확인할 필요가 없는 인덱스는 건너뛰는 것입니다. 먼저 match인 경우는 텍스트 문자열과 쿼리 문자열의의 탐색 위치를 1씩 증가시킵니다. 아래 그림을 보면 인덱스 0~6에서는 match, 7에서 dismatch가 발생했습니다.

    dismatch가 발생하면 쿼리문자열의 다음 탐색 위치를 찾기 위해 pi 배열의 dismatch 직전 위치에 해당하는 값을 참조합니다. 즉, pi[7-1]을 찾으면 된다. 예시에서 pi[6]은 prefix, suffix가 같은 최대 문자열이 AA이므로 2일 것입니다. 그럼 이제 아래 그림처럼 i=7 위치에서 j=2부터 다시 비교를 시작합니다.

    다시 dismatch가 발생했고, 이제 j=pi[2-1]=1 위치부터 비교합니다. 마찬가지로 mismatch이므로 pi[0]=0 위치로 돌아옵니다. 즉, 쿼리문자열의 처음부터 비교하는 것입니다. 이후 mismatch 상황에서는 i만 증가하면 됩니다.

이게 왜 O(n)이지?

    방금 예시에서 i=7 위치 한 곳에서 계속 반복문을 도는 모습을 보니 '이거 O(n) 아닐수도 있지 않나?'라는 생각이 들었습니다. 이것을 아주 깔끔히 설명해주는 글이 있습니다. 핵심만 말하면, 전체 i에 대해 쿼리 문자열의 인덱스 j가 증가하고 감소하는 횟수는 다 더해도 최악의 경우 n번이며, 따라서 O(n+n)=O(n)이라는 것입니다.

4. 구현 코드

    아래는 대상문자열 S, 쿼리문자열을 P라고 했을 때 pi 배열을 얻고 문자열 탐색과정을 나타낸 함수입니다. 일단 간단하게 일치하는 문자열을 찾자마자 1을 반환하고, 없으면 0을 반환하는 식으로 구현했는데요, 모든 일치 문자열의 그 위치를 찾으려면 Integer형 List를 반환하고, j==P.length() 조건을 만족할 때 return이 아니라 list에 인덱스를 추가하고 j=pi[j-1];로 바꿔주면 됩니다.

public int kmp(String S, String P) {
    int[] pi = getPi(P);
    int i = 0, j = 0;   // i : S index, j : P index
    while (i < S.length()) {
        if (S.charAt(i) == P.charAt(j)) {   // match
            i++;
            j++;
            if (j == P.length()) {
                return 1;
            }
        } else {    // mismatch
            if (j != 0) {
                j = pi[j - 1];  // pi 배열 값만큼 건너뛰기
            } else {
                i++;
            }
        }
    }
    return 0;
}

4. 여담 - 왜 java는 KMP를 구현하지 않았을까?

    스택 오버플로우 답변