3 min to read

KMP에 대해 배워봅시다.

KMP에 대해 배워봅시다.

Imagem de capa

안녕하세요! 오늘은 kmp에 대해서 알아보도록해요. 이 이론에 대해서 자세히 나와있는 블로그를 소개해드릴게요!

kmp 설명

링크에는 c++로 풀이를 하셨지만, 저는 java로 보여드리겠습니다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		String pattern=br.readLine();
		ArrayList<Integer> list = kmp(s, pattern);
		System.out.println(list.size());
		for(int i=0;i<list.size();i++){
			System.out.print((list.get(i)+1)+" ");
		}

	}

	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;
	}

	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();

		for (int i = 0; i < n; i++) {
			while (j > 0 && s[i] != p[j]) {
				j = pi[j - 1];
			}

			if (s[i] == p[j]) {
				//패턴이 끝까지 같다면 리스트에 위치를 저장합니다.
				if (j == m - 1) {
					list.add(i - m + 1);
					j = pi[j];
				} else {
					j++;
				}
			}
		}
		return list;
	}
}