Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

1. 찾기

1786번

문자열 T에서 문자열 P가 있는지 찾는 알고리즘인 KMP 알고리즘을 배우는 문제

이번 문제는 주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 문제이다.

유명한 알고리즘인 KMP 알고리즘을 활용하여 구현할 수 있다.
KMP 알고리즘(커누스-모리스-프랫 알고리즘)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다.
문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi) 를 사용한다.

1) 찾으려는 문자열의 접두사와 접미사 길이를 담은 배열 pi

2) pi를 활용해, 전체 문자열에서 중복을 제거해며 일치하는 문자열이 있는지 확인

3) 문자열의 시작 위치 인덱스를 리스트에.

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	static List<Integer> list;

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

		String T = br.readLine();
		String P = br.readLine();

		list = new ArrayList<Integer>();
		KMP(T, P);

		bw.write(list.size() + "\n");
		for (int l : list) {
			bw.write(l + " ");
		}

		bw.flush();
		bw.close();
		br.close();
	}

	public static void KMP(String o, String p) {
		int pi[] = getPi(p);
		int j = 0;
		for (int i = 0; i < o.length(); i++) {
			while (j > 0 && o.charAt(i) != p.charAt(j)) {
				j = pi[j - 1];
			}
			if (o.charAt(i) == p.charAt(j)) {
				if (j + 1 == p.length()) {
					list.add(i - p.length() + 2);
					j = pi[j];
				} else {
					j++;
				}
			}
		}
	}

	public static int[] getPi(String pattern) {
		int[] pi = new int[pattern.length()];
		int j = 0;
		for (int i = 1; i < pattern.length(); i++) {
			while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
				j = pi[j - 1];
			}
			if (pattern.charAt(i) == pattern.charAt(j))
				pi[i] = ++j;
		}
		return pi;
	}
}

• Python

def getPi():
    pi = [0 for _ in range(0, len(P))]
    j = 0
    
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]

        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi


def KMP(pi):
    result = []
    cnt = 0
    j = 0
    for i in range(0, len(T)):

        while j > 0 and T[i] != P[j]:
            j = pi[j - 1]

        if T[i] == P[j]:
            if j == (len(P) - 1):
                result.append(i - len(P) + 2)
                cnt += 1
                j = pi[j]
            else:
                j += 1

    print(cnt)
    for l in result:
        print(l)


T = input()
P = input()
KMP(getPi())