본문 바로가기
알고리즘/String

IOIOI(KMP 알고리즘)

by 히포파타마스 2024. 6. 10.

IOIOI

 

백준 5525번 문제

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

 

5525번: IOIOI

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇

www.acmicpc.net

 

 

 

1. 문제

 

 

 

 

2. 풀이

2.1 KMP 알고리즘

2.1.1 아이디어

이 문제는 주어진 문장열에서 특정 문자열이 몇 개나 있는지를 찾는 문제이다.

이 문제는 다음과 같이 단순하게 문자열의 단어를 처음부터 비교하는 것으로 해결할 수 있다.

주어진 각 문자열이 다음과 같다고 하자.

 

[단어 찾기 그_1]

 

[단어 찾기 그_2]

 

문자열의 처음부터 찾으려는 문자열의 처음과 비교한다. 

위와 같이 단어가 일치하지 않는다면 다음 문자부터 다시 비교한다.

 

[단어 찾기 그_3]

 

[단어 찾기 그_4]

 

[단어 찾기 그_5]

 

[단어 찾기 그_6]

 

[단어 찾기 그_7]

 

이런식으로 문자열의 모든 위치에서 단어를 비교하면 우리가 찾는 특정 문자열이 비교되고 있는 문자열에 있는지 없는지를 파악할 수 있다.

하지만 이 방식은 시간복잡도가 O(NM)으로 비효율적이다.

 

위의 방식에서는 문자열의 문자를 비교하며 문자가 틀렸다는 정보만을 파악하고 다음 문자를 비교했다.

각 문자열을 비교할 때 틀렸다는 정보 외에도 일치했다는 정보를 활용할 수는 없을까?

 

예를 들어 앞의 예시에서 문자열의 첫 부분부터 단어를 비교했을 때를 보자.

 

[틀린정보 활용 그_1]

 

여기서 비교하는 문자가 틀려서 문자열의 다음으로 넘어가기 전에 일치했던 부분을 다시 확인해 보자.

 

[틀린 정보 활용 그_2]

 

일치했던 부분을 보면 두 번째까지의 접두사와 접미사가 일치하는 것을 알 수 있다.

 

이 정보를 활용하면 문자열의 두 번째부터 다시 비교하지 않을 수 있다.

 

[틀린 정보 활용 그_3]

 

두 번째까지 접두사와 접미사가 같기 때문에 위와 같이 문자열의 세 번째 위치부터 네 번째까지 총두 개의 문자가 일치한다는 사실을 알 수 있다. 때문에 우리는 이 정보를 가지고 비교되는 문자열의 다섯 번째부터 단어를 비교하면 된다.

 

이와 같이 각 문자열을 비교했을 때 일치했었던 부분의 정보까지 활용해서 단어를 찾는 방법이 KMP 알고리즘의 주요 아이디어이다.

위 예시와 같이 KMP 알고리즘을 사용하기 위해서는 문자열의 부분문자열 중 접두사=접미사가 될 수 있는 가장 긴 부분 문자열을 파악해야 된다.

 

 

2.1.2 p 배열 구하기

p[i]를 0~i 까지의 부분 문자열 중에서 접두사=접미사가 될 수 있는 가장 긴 부분문자열이라고 하자.

다음과 같은 표를 통해서 p[i]를 파악할 수 있다.

 

[p[i] 표]

 

문자열이 주어졌을 때 p[i] 배열은 어떻게 구할까?

가장 단순한 방법은 문자열의 첫 부분부터 하나하나씩 비교하는 것이다.

 

여기서는 예시를 돕기 위해 "ABAABAB"의 p[i]를 구해본다.

 

[p[i] 배열 구하기 그_1]

 

[p[i] 배열 구하기 그_2]

 

[p[i] 배열 구하기 그_3]

 

[p[i] 배열 구하기 그_4]

 

[p[i] 배열 구하기 그_5]

 

이런 식으로 문자와 문자를 처음부터 비교해 가며 p[i] 배열을 구할 수도 있지만 이래서야 앞서 문자열에서 특정 문자열을 찾기 위해 문자열의 처음부터 하나씩 문자를 비교 탐색하던 방법과 같이 비효율적이게 된다.

 

그래서 p[i] 배열을 구할 때도 문자가 일치했던 정보를 사용한다.

 

앞서 예시를 더 진행해 보자.

 

[p[i] 배열 구하기 그_6]

 

첫 번째 문자열의 7(i)번째와 두 번째 문자열의 4(j)번째 문자가 불일치했다.

여기서 i(7)를 5로 j(4)를 1로 돌려서 다시 비교해야 할까?

답은 '아니다' 이다.

우리는 두 번째 문자열의 3(j)번째 까지 첫 번째 문자와 일치했음을 알고 있다.

그리고 p[3] = 1이다. 

이 말은 일치한 부분 문자열(ABA)중 접두사와 접미사가 일치하는 가장 긴 문자열의 길이가 1임을 의미한다.

때문에 첫 번째 문자열의 6(i)번째와 두 번째 문자열의 1(j)번째 문자가 일치함을 알고 있다.

위 정보를 토대로 다음과 같이 문자열을 하나씩 넘어가지 않고 중간 과정을 생략할 수 있다.

 

[p[i] 배열 구하기 그_7]

 

i = 7로 첫 번째 문자열의 마지막까지 왔기 때문에 여기서 탐색을 멈추고 p[i] 배열을 완성시킬 수 있다. 

 

p[i]를 구하는 코드는 다음과 같다.

 

[caculateP]

private static void calculateP(int[] p, String target) {
    int j = 0;
    for (int i = 1; i < target.length(); i++) {
        while (j > 0 && target.charAt(i) != target.charAt(j)) {
            j = p[j - 1];
        }
        if (target.charAt(i) == target.charAt(j)) {
            p[i] = ++j;
        }
    }
}

 

위의 예시와 같이 i는 비교되는 문자열(target)의 문자위치를 뜻하고 j는 비교하는 문자열(target)의 위치를 의미한다.

탐색은 i가 마지막 인덱스까지 갈 때까지 탐색한다.

i와 j 위치의 문자를 비교하며 틀렸을 경우 j = [p - 1]로 되돌린다.

만약 i와 j 위치의 문자가 또 틀리다면 j = [p - 1]로 되돌린다.

이를 j가 첫 번째(=0)가 될 때까지 반복한다. 코드에서는 while문으로 구현되었다.

만약 i와 j 위치의 문자가 일치할 경우 p[i] = j + 1로 기록한다.

 

위의 코드를 토대로 "ABABABAC"의 p[i] 배열을 구해보면 다음과 같다.

 

[p[i] 배열 구하기 그_8]

 

문자가 불일치하고 j = 0이므로 i = 2부터 다시 비교한다.

 

[p[i] 배열 구하기 그_9]

 

문자가 일치하기 때문에 p[2] = 0 + 1로 기록한다.

 

[p[i] 배열 구하기 그_10]

 

연속해서 문자가 일치하기 때문에 p[i]를 기록한다.

 

[p[i] 배열 구하기 그_11]

 

문자가 틀렸으니 j = p[4]로 돌아가서 다시 비교한다.

 

[p[i] 배열 구하기 그_12]

 

문자가 틀렸으니 j = p[2]로 돌아가서 다시 비교한다.

 

[p[i] 배열 구하기 그_13]

 

문자가 틀렸으니 j = p[0]로 돌아가서 다시 비교한다.

 

[p[i] 배열 구하기 그_14]

 

문자가 틀렸고 j = 0으로 문자열의 첫 번째이기 때문에 p[7]은 0이 된다.

 

 

2.1.3 KMP 알고리즘을 사용해서 문자열에서 문자 찾기

부분문자열의 접두사와 접미사가 같은 가장 긴 부분문자열의 길이를 알았으니 이를 토대로 문자열에서 특정 문자열을 찾는다.

코드는 다음과 같다.

 

[countWordByKMP]

private static int countWordByKMP(int[] p, String string, String target) {
    int count = 0;
    int j = 0;
    for (int i = 0; i < string.length(); i++) {
        while (j > 0 && string.charAt(i) != target.charAt(j)) {
            j = p[j - 1];
        }
        if (string.charAt(i) == target.charAt(j)) {
            if (j == target.length() - 1) {
                count++;
                j = p[j];
            } else {
                j++;
            }
        }
    }

    return count;
}

 

i는 주어진 문자열의 위치를 뜻하며 j는 찾으려는 문자열인 target의 위치를 의미한다.

앞선 예시에서 나왔던 것과 같이 비교한 문자가 틀리면 다음 문자로 하나씩 넘어가는 것이 아니라 p[i]배열을 활용해 중간 단계를 건너뛴다.

문자가 일치하고 target과 일치하는 부분문자열이 있다면 count를 +1 해준다.

이 경우에도 문자열의 다음 문자로 넘어가는 게 아니라 p 배열을 활용해 중간단계를 건너뛴다.

이와 같은 방식으로 count를 구해 문자열에 찾으려는 문자열이 몇 개 존재하는지를 구한다.

 

위 코드에 대한 예시는 다음과 같다.

 

[KMP예 그_1]

 

[KMP예 그_2]

 

j = 4 에서 문자가 일치하지 않았으므로 j = p[3] = 2로 한 후 i = 4 부터 다시 비교를 진행한다.

 

[KMP예 그_3]

 

j = 2 에서 문자가 일치하지 않았으므로 j = p[1] = 0으로 한 후 i = 4 부터 다시 비교를 진행한다.

 

[KMP예 그_4]

 

j = 0이고 문자가 일치하지 않았기 때문에 i를 +1 해주고 다시 비교를 시작한다.

 

[KMP예 그_5]

 

j의 마지막 열까지 문자가 일치했으므로 count에 1을 더해준다.

추가로 j = p[4] = 3으로 한 후 현재 i에 1을 더한 i = 10과 비교를 시작한다. 

 

[KMP예 그_6]

 

i가 마지막 문자에 도달했기 때문에 탐색을 종료한다.

 

 

3. 전체 코드

[전체 코드]

import java.io.*;

public class IOIOI_5525 {

    private static void calculateP(int[] p, String target) {
        int j = 0;
        for (int i = 1; i < target.length(); i++) {
            while (j > 0 && target.charAt(i) != target.charAt(j)) {
                j = p[j - 1];
            }
            if (target.charAt(i) == target.charAt(j)) {
                p[i] = ++j;
            }
        }
    }

    private static int countWordByKMP(int[] p, String string, String target) {
        int count = 0;
        int j = 0;
        for (int i = 0; i < string.length(); i++) {
            while (j > 0 && string.charAt(i) != target.charAt(j)) {
                j = p[j - 1];
            }
            if (string.charAt(i) == target.charAt(j)) {
                if (j == target.length() - 1) {
                    count++;
                    j = p[j];
                } else {
                    j++;
                }
            }
        }

        return count;
    }

    private static String createIO(int n) {
        StringBuilder sb = new StringBuilder();
        sb.append('I');
        for (int i = 0; i < n; i++) {
            sb.append("OI");
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String word = createIO(n);

        int sentenceLength = Integer.parseInt(br.readLine());
        String sentence = br.readLine();

        int[] p = new int[word.length()];
        calculateP(p, word);

        int count = countWordByKMP(p, sentence, word);

        bw.write(String.valueOf(count));
        bw.flush();
    }
}

'알고리즘 > String' 카테고리의 다른 글

순한 수열  (0) 2023.01.21
회-문  (0) 2022.08.31

댓글