• 문자열 검색 KMP 알고리즘 :: 마이구미
    알고리즘 2016. 10. 28. 19:11
    반응형

    이번 글은 KMP 알고리즘에 대해 다룰 것이다.

    KMP 알고리즘이란 무엇인가?

    이름에 대해서는 큰 의미가 없다. 그냥 사람 이름이다.


    백준 5525번, 10769번, 1786번을 풀다가 알게 된 알고리즘이다.

    유용한 알고리즘이기에 한명이라도 더 알리기 위해 글로 다루게 되었다. (복습 목적이지만..^^)


    그렇다면 어떤 알고리즘인가? 어떤 경우에 사용하는 알고리즘인가?

    시작해보자.

    시작하기에 앞서 목적은 문자열 검색에 사용되는 알고리즘이다.


    문자열 검색의 예를 들어보자.

    문자열 ABCEDFRIEPQJDNVABRIDFNIABC 라는 문자열이 있을 때 ABCEF라는 문자열을 찾아보자.

    여러분들은 어떻게 하겠는가?

    가장 순진한 방법을 말해보겠다.


    ABCEDABCEFQJDNVABRIDFNIABC 

    ABCEF

    ABCEDFRIEPQJDNVABRIDFNIABC

      ABCEF

    ABCEDFRIEPQJDNVABRIDFNIABC

        ABCEF

    ABCEDFRIEPQJDNVABRIDFNIABC

            ABCEF


    가장 기본적으로 위와 같이 한자리씩 이동하면서 비교하는 방법을 사용할 수 있다.

    이러한 방법을 이용하면 보다시피 문자열이 길어질수록 비교횟수가 훨씬 더 증가하는 것을 알 수 있다.

    빅오표기법으로 O(전체 문자열 크기*찾을 문자열 크기) 이 될 것이다.

    이를 해결하기 위한 방법이 KMP 알고리즘을 이용할 수 있다.

    KMP 알고리즘을 이용할 시 O(문자열 크기 + 찾을 문자열 크기) 로 처리할 수 있다.


    그렇다면 이제 KMP 알고리즘에 대해 본격적으로 알아보자.

    일단 어떤 식으로 돌아가는 지 수박 겉을 핥아보자.


    기본적인 방법처럼 문자열을 한자리씩 옮기면서 비교하면서 어떻게 하면 불필요한 부분을 넘길 수 있을까?

    KMP 알고리즘의 핵심은 이전에 비교한 정보를 활용하여 검색하는 것이다.

    예를 들어보자. 


    ABCDABCDABEE에서 ABCDABE를 찾을 경우를 보자.

    ABCDAB 까지는 동일하지만 마지막 요소가 다르다.

    이 경우 기본적인 방법의 경우에는 다시 한자리를 증가하여 비교하게 된다.

    KMP 알고리즘의 경우에는 ABCDAB까지 같았다는 정보를 가지고 그 다음 비교를 정하게 된다.


    KMP 알고리즘을 알기 위해선 기본적으로 접두사와 접미사의 개념이 필요하다.

    간단하게 접두사란 앞에 붙이는 단어, 접미사란 뒤에 붙이는 단어라고 찾아볼 수 있을 것이다.

    예를 들어보자.

    ABCDAB

    접두사 - A, AB, ABC, ABCD, ABCDA, ABCDAB

    접미사 - B, BA, BAD, BADC, BADCB, BADCBA

    그냥 접두사는 앞에서부터 잘랐고, 접미사는 뒤에서부터 잘랐다.


    그렇다면 0~i까지 문자열 중 접미사와 접두사가 같을 경우의 가장 긴 길이를 구할 것이다.

    아래의 예를 보면서 이해를 해보자.

    AAABAA

    A - 0

    AA - 1

    AA- 2

    AAAB - 0

    AAABA - 1

    AAABAA - 2


    ABCDAB

    A - 0

    AB - 0

    ABC - 0

    ABCD - 0

    ABCDA - 1

    ABCDAB - 2


    이것을 활용하여 불필요한 부분을 넘길 때 사용하는 PI라는 배열을 만들 것이다.

    여기서 의문이 들 수도 있다.

    왜 접미사와 접두사가 같은 경우를 조건으로 들까?

    불필요한 부분을 넘길 때에 주의할 점은 넘기고 그 전에 찾을 문자열이 포함된 것이 있는지 한번 확인해봐야한다.


    예를 들면, AAAABAAAAC 문자열에서 AAAAC를 찾을 땐 인덱스 4에서 같지 않으니 그냥 바로 인덱스 5로 넘겨 비교하면 된다.

    그래서 그냥 같지 않다 싶으면 찾을 문자열 크기만큼 인덱스를 넘겨버리면 되겠다 생각할 수 있다.


    AAAABAAAAC

    => 크기만큼 건너뛰기

    AAAABAAAAC


    하지만 예외가 발생한다.

    ABCDABCDABEAAAA 문자열에서 ABCDABE를 찾을 경우에는 인덱스 6에서 틀리기 때문에, 크기만큼 넘겨보자.


    ABCDABCDABEAAAA

    => 크기만큼 건너뛰기

    ABCDABCDABEAAAA


    인덱스 6 전에 인덱스 4,5의 요소 AB라는 녀석 => 찾을 문자열에 포함되는 녀석이 있다.

    무작정 크기를 통해 넘기면 안되는 것을 확인했다.

    그렇기 때문에 접두사와 접미사가 같은 것을 기준으로 PI배열을 만드는 것이다.


    그렇다면 kmp 알고리즘 주요 코드를 보자.


    public static ArrayList<Integer> kmp(String str, String pattern) { ArrayList<Integer> list = new ArrayList<Integer>(); int[] pi = getPi(pattern); int n = str.length(), m = pattern.length(), j = 0; char[] s = str.toCharArray(); char[] p = pattern.toCharArray();         // str - 전체 문자열, pattern - 찾을 문자열 // j - 찾을 문자열의 비교 인덱스. // i - 전체 문자열과 비교할 인덱스이기 때문에 1씩 증가하기만 함. 절대 불규칙적으로 변경되지 않음. for (int i = 0; i < n; i++) { while (j > 0 && s[i] != p[j]) { // 중간 단계 뛰어넘기. // pi배열을 이용하여 j인덱스를 변경시킴으로써 while문 중단. j = pi[j - 1]; } if (s[i] == p[j]) { if (j == m - 1) { // j는 비교 인덱스로써, 인덱스가 찾을 문자열의 크기에 도달하면 문자열 찾음. list.add(i - m + 1); // 여러 개의 찾을 문자열이 있을 수 있기 때문. j = pi[j]; } else { j++; } } } return list; }


    위 코드에서는 한 부분만 이해한다면 크게 문제없다.

    아래를 보자.


    while (j > 0 && s[i] != p[j]) { // 중간 단계 뛰어넘기. // pi배열을 이용하여 j인덱스를 변경시킴으로써 while문 중단. j = pi[j - 1]; }


    중간 단계 부분을 뛰어넘는 부분이다.

    i는 전체 문자열의 비교할 인덱스이고, j는 찾을 문자열의 인덱스인 점을 인지하고 있어야한다.

    비교할 인덱스 i의 요소와 찾을 문자열 인덱스 j의 요소가 다르다면 pi배열에 들어있는 값을 이용하여 j를 변경시키는 것이다.

    이렇게 pi배열을 통해 j를 변경시킴으로써 이전의 일치했던 정보들을 그대로 다시 활용할 수 있어 불필요한 단계를 넘길 수 있게 된다.

    여기서 i 인덱스는 1씩 증가하는 전체 문자열의 인덱스일 뿐이고, j 인덱스가 계속해서 변경되는 찾을 문자열의 인덱스인 점을 생각하자.

    i는 생각할 것이 없다. 

    j가 어떻게 변해서 어떻게 활용되는지만 이해하면 된다.


    kmp 함수의 원리를 그대로 이용하여 pi배열을 만들 수 있다.

    PI배열을 만드는 소스로 보자.


    public static int[] getPi(String pattern) {

    int m = pattern.length();

    int j = 0;

    char[] p = new char[m];

    int[] pi = new int[m];


    p = pattern.toCharArray();


    for (int i = 1; i < m; i++) {

    while (j > 0 && p[i] != p[j]) {

    j = pi[j - 1];

    }

    if (p[i] == p[j]) {

    pi[i] = ++j;

    }

    }


    return pi;

    }


    kmp 함수를 이해한다면 pi배열을 만드는 부분도 이해할 수 있다.

    여러번 반복해서 읽어보자.


    본인이 참고한 링크이다.

    http://bowbowbow.tistory.com/6#comment5168448

    위의 링크를 참고하여 글을 다뤘다.

    본인은 여러번 봐야 이해를 할 수 있었다. 

    조금 더 쉽게 다룰려고 했으나, 잘 모르겠다.


    KMP 관련 문제 소스 Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/kmp


    백준 알고리즘 5525번 IOIOI

    https://www.acmicpc.net/problem/5525


    백준 알고리즘 10769번 행복한지 슬픈지

    https://www.acmicpc.net/problem/10769


    백준 알고리즘 1786번 찾기

    https://www.acmicpc.net/problem/1786



    반응형

    댓글 25

    • occidere 2016.12.08 00:12

      잘 보고 갑니다!
      아직 실력이 부족한지 쉽게 이해가 되진 않지만 그래도 계속 이해하려고 노력해봐야겠네요

    • kevinsungcjh 2017.01.20 02:03

      코드복붙해봤는데 컴파일했는데 결과가 아무것도 안나오네여 ..?

    • Pcw 2017.03.25 15:10

      감사합니다 많은 도움이 됐습니다

    • 지나가던 사람 2019.05.03 08:57

      PI 구하는 예시에서 첫 번째의 AAABA 값은 앞뒤로 A가 존재하니까 1 아닌가요?

      그리구 다음 예시에서 ABCDAB의 다섯번째가 ABCDB라고 잘못 나와있네요 ~~

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.05.03 21:18 신고

      작성자 - PASUDO | 2 years ago

      안녕하세요 KMP 알고리즘 관련해서 공부하다가 여기까지 왔습니다. 물론 참고하신 분의 링크도 있어서 그거 확인하고 이후에 자바코드로 여기까지 와서 보고있습니다. 약간 궁금한 점이 있어서 묻습니다.
      KMP 알고리즘 내에서 중간단계를 뛰어넘기 위한 코드 부분 j = pi[j - 1]; 이 부분은 이전 prefix 와 suffix 부분에서 가장 긴 문자열을 리턴해서, 이후에 불필요한 비교연산을 줄이기 위함은 이해했습니다만 그 밑에서 이제 j 가 패턴 문자열 마지막 인덱스에 도달한 경우 j = pi[j]; 이 부분에서는 j = 0 으로 바꾸어주어야 하는 것이 아닌지 잠깐 생각해보았습니다.
      하지만 그렇게 하는 경우 반례가 생기더군요..
      제가 찾은 부분은
text :: ABDABCABCABABCABF
pattern :: ABCA
라고 한 부분에서
      j = 0 으로 바꾸어버리면 패턴을 찾을 수 있는 곳은 두 곳 밖에 존재하지 않더군요. 인덱스 기준으로 3번 인덱스와 11번 인덱스이고.
j = pi[j] 로 한 부분에서는 3번 인덱스와 6번 인덱스 그리고 11번 인덱스를 찾을 수 있다고 하여서 저렇게 한 것 같습니다.
      제가 코드만 보고 이해한 것이기 때문에 정확하지 않지만 제가 생각한 부분이 맞는지 여쭤보고 싶네요.
      --
      금방 코드를 짜서 위의 예시에 코드를 바꾸어서 결과값을 보니, 제가 생각한 부분이 맞네요 ㅎㅎ

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.05.03 21:18 신고

        댓글을 확인하지 못했었네요.. 읽어주셔서 감사합니다!
자문자답 하신 것을 토대로 간략히 적어놓겠습니다.
        AABAABBAA
AABAA
주어졌을 경우, 찾을 수 있는 문자열의 개수는 인덱스 0, 3으로써 2개가 됩니다.
j = 0을 줬을 경우, pattern의 인덱스 0과 text 문자열의 인덱스 5가 비교되기 때문에 말씀하신 반례가 생깁니다.
위의 반례처럼 찾은 문자열을 포함하면서 찾을 수 있는 패턴도 존재합니다.
이 경우, 패턴의 접미사와 접두사가 같을 경우의 가장 긴 문자열의 길이(pi) 를 통해 건너뛰어 해결할 수 있습니다.

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.05.08 14:03 신고

      작성자 HW J / 2018.8
      m-1까지 도달하고 나서 j=pi[j]인 부분이 잘 이해가 되지 않았는데 덕분에 명확해졌습니다. 감사합니다.

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.05.08 14:03 신고

      작성자 이반호 / 2018
      10769번 , 1786번 푸신 것은 없으신건가요!?

    • 2019.10.08 22:03

      비밀댓글입니다

    • 알고싶다 2019.12.05 10:05

      AAA 일때 {0,1,2} 아닌가요??

    • 알고싶다 2019.12.05 15:47

      getPi( "AAA" ) 하면 결과가 {0,1,2} 아닌가요??
      위에 예시에서 AAABAA 의 경우 3번째 AAA - 1이라고 되어 있는데 2인거 같아서요

    • KMP알고리즘만 한달째 2019.12.05 15:47

      getPi함수에 AAA 돌리면
      011 아니고 012 로 나오는데 뭐가 맞는걸까요??

    • Favicon of https://lts0606.tistory.com 마샤와 곰 2020.02.19 10:04 신고

      정리가 잘되어 있네요. 재미있게보고갑니다. ^-^

    • 잔나장인어른 2020.06.08 10:19

      ABCDA 에서 0이라구 하셨는데 1을 0으로 오타로 적으신건가요?
      도움많이됩니다^^

    • Favicon of https://devms.tistory.com Angloper 2021.05.18 15:26 신고

      ABCDAB의접미사는
      B, AB, DAB, CDAB, BCDAB, ABCDAB 여야하는거아닌가요?

Designed by Tistory.