[Java] Java로 풀면 KMP를 써야하는 브론즈 문제가 있다?

알고리즘 글 아닙니다.

관련 링크 : https://www.acmicpc.net/problem/16916

 

 약 1년 전, 백준 스트릭을 유지하던 때가 있었습니다. 자바로 코테 준비를 시작한 지 얼마 안 됐기도 하고, 여러 가지 준비로 바빠서 가볍게 몸풀기로 푸려던 문제 중 하나였습니다. 간단하게 contains를 하면 되지 않을까 싶었지만?

 

import java.io.*;
import java.util.*;
public class Main {
    //12:56-
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine(), p = br.readLine();
        System.out.println(s.contains(p) ? "1" : "0");

    }
}

 

...

 시간 초과가 나버렸습니다. contains의 구조를 뜯어볼 수밖에 없겠죠? 메서드를 타고 타고 들어가 봅시다.

 

 

contains

indexOf

indexOf

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

 Java의 indexOf()는 Brute-Force 알고리즘입니다. 문자열의 길이가 짧으면 쓸만한 메서드긴 하지만, 문자열 S의 모든 문자에 대해 문자열 P와 비교해야 하므로 시간 복잡도는 O(N*M)이 됩니다. 100만 * 100만 = 1조가 됩니다.. 이러니 시간초과가 걸릴 수밖에 없죠.

 

그러면 Java는 어떻게 해야 하나요..

 하는 수 없이 고급 알고리즘을 써야겠죠. 바로 KMP 문자열 패턴 매칭 알고리즘입니다. 1년 전에도 이와 관련해서 블로그 게시글을 작성하던 적이 있거든요. 전공 시간에 배웠던 기억 되살려서 설명 좀 하려고 했더니 임시 저장글이 날아가버렸었습니다.. Knuth, Morris, Pratt 아저씨들이 만든 알고리즘이라 KMP라고 이름이 붙었습니다. KMP와 관련해서는 다른 블로그에서 잘 정리해 놓은 자료가 있으니 참고하시면 되겠습니다. (바로가기)

 

 핵심은 반복되는 계산을 피하는 겁니다. 문자열 패턴을 이용해서 부분일치 테이블 배열을 만든 후(M), 이를 활용하여 패턴 검색(N)을 하는 것입니다. 이미 일치하는 부분을 기억하면서 불필요한 비교를 줄이는 것이죠. 시간 복잡도가 O(N+M)이 되므로 TLE이 발생하지 않게 됩니다.

 

---

 

 그런데, Python으로 풀면 어떻게 될까요?

a = input();
b = input();
if b in a :
	print(1);
else :
	print(0);

 

 Python 3.10부터 in 연산자의 알고리즘이 개선되면서 최악일 경우 O(N+M)인 시간 복잡도가 나오게 됐다고 합니다.

 

Runtime of python's if substring in string

cpython/Objects/stringlib/fastsearch.h at main · python/cpython

cpython/Objects/stringlib/stringlib_find_two_way_notes.txt at main · python/cpython

Two-way string-matching algorithm - Wikipedia

 

 KMP와 Boyer-Moore 알고리즘을 조합한 Two-way string-matching 알고리즘을 쓴다고 합니다.

 

 이해한 바로 Python 버전이 낮을 때는 in 연산자가 문자열 검색을 수행할 때, 실제로는 C로 작성된 함수 str.__contains__() 메서드를 호출하구요. 그러면 memmem()이나 strstr() 함수를 사용해서 문자열 검색을 수행하는데, 플랫폼에 따라 다릅니다. memmem()을 지원하지 않으면 strstr()을 사용해요. strstr()은 플랫폼마다 구현의 최적화 정도가 달라서 성능이 떨어질 수도 있었죠. 하지만? Python 3.10부터는 자체 구현된 알고리즘을 통해 strstr()에 의존하지 않게 되었다-정도로 볼 수 있을 것 같습니다.

 

---

 

근데 C에서는 strstr()로도 통과했다던데요..

 그러게 말입니다. 제가 알고 있었고 나름 따라서 구현해보려 했던 strstr() 코드는 다음 코드랑 비슷했었습니다.

#include <stddef.h>

extern char *strchr (const char *, int);
extern int strncmp (const void *, const void *, size_t);
extern size_t strlen (const char *);

char *
strstr (const char *s1, const char *s2)
{
  const char *p = s1;
  const size_t len = strlen (s2);

  if (!len)
    return s1;

  for (; (p = strchr (p, *s2)) != 0; p++)
    {
      if (strncmp (p, s2, len) == 0)
	return (char *)p;
    }
  return (0);
}

 그냥 뭐 이것도 Brute-Force스럽습니다. 당연히 strstr()이 요렇게 구현되어 있을 리가 없죠. 그러면 통과를 못했을 테니.

 

 

BOJ

 저도 찾다가 발견한 건데 대부분 블로그에서 딱 저 내용만 붙어있었습니다. 왜 O(N+M)인지는 안 적혀있길래 좀 더 들어가 봤습니다.

glibc/string/strstr.c at master · lattera/glibc

#ifndef _LIBC
# include <config.h>
#endif

/* Specification of strstr.  */
#include <string.h>

#include <stdbool.h>

#ifndef _LIBC
# define __builtin_expect(expr, val)   (expr)
#endif

#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l)			\
  (((j) + (n_l) <= (h_l)) || ((h_l) += __strnlen ((void*)((h) + (h_l)), 512), \
			      (j) + (n_l) <= (h_l)))
#define CHECK_EOL (1)
#define RET0_IF_0(a) if (!a) goto ret0
#define FASTSEARCH(S,C,N) (void*) strchr ((void*)(S), (C))
#include "str-two-way.h"

#undef strstr

#ifndef STRSTR
#define STRSTR strstr
#endif

/* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
   if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
   HAYSTACK.  */
char *
STRSTR (const char *haystack, const char *needle)
{
  size_t needle_len; /* Length of NEEDLE.  */
  size_t haystack_len; /* Known minimum length of HAYSTACK.  */

  /* Handle empty NEEDLE special case.  */
  if (needle[0] == '\0')
    return (char *) haystack;

  /* Skip until we find the first matching char from NEEDLE.  */
  haystack = strchr (haystack, needle[0]);
  if (haystack == NULL || needle[1] == '\0')
    return (char *) haystack;

  /* Ensure HAYSTACK length is at least as long as NEEDLE length.
     Since a match may occur early on in a huge HAYSTACK, use strnlen
     and read ahead a few cachelines for improved performance.  */
  needle_len = strlen (needle);
  haystack_len = __strnlen (haystack, needle_len + 256);
  if (haystack_len < needle_len)
    return NULL;

  /* Check whether we have a match.  This improves performance since we avoid
     the initialization overhead of the two-way algorithm.  */
  if (memcmp (haystack, needle, needle_len) == 0)
    return (char *) haystack;

  /* Perform the search.  Abstract memory is considered to be an array
     of 'unsigned char' values, not an array of 'char' values.  See
     ISO C 99 section 6.2.6.1.  */
  if (needle_len < LONG_NEEDLE_THRESHOLD)
    return two_way_short_needle ((const unsigned char *) haystack,
				 haystack_len,
				 (const unsigned char *) needle, needle_len);
  return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
			      (const unsigned char *) needle, needle_len);
}
libc_hidden_builtin_def (strstr)

#undef LONG_NEEDLE_THRESHOLD

 

two-way

 중간에 코드를 잘 보면 str-two-way.h 파일을 include 하는 것을 볼 수 있습니다. 정말로 Two-way string-matching 알고리즘이 구현되어 있는가를 찾아봅시다.

 

 

glibc/string/str-two-way.h at master · lattera/glibc

Comment

 여기서 Two-way string-matching 알고리즘을 사용한다고 주석을 달아놨습니다. 아무튼 뭐 이런 맥락으로 C 쪽도 strstr()로 통과가 되는 것 같습니다.

 

 

1년 전에 궁금했던 거 다시 꺼내서 알아보려니까 재밌긴 한데 시간이...