[알고리즘] 찾기 KMP (백준 1786번)

1786번: 찾기

 

 정확하게 KMP를 구현하는 문제다. 패턴 매칭 실패 시 패턴 인덱스 j 가 돌아갈 곳을 지정하는 failureFunction을 구하는 메서드와 그걸 이용해서 패턴 매칭을 하는 KMP 메서드로 이루어져있다.

 

 주로 겹쳐져있는 패턴도 찾아낼 때에 사용한다.

EX) 텍스트 : ababa, 패턴 : aba → 패턴 개수 : 2개

String.replace로는 찾아낼 수 없는 경우임

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static void failureFunction(int p[], char[] pattern)
	{
		int j = 0;

		for(int i = 1;i < pattern.length;i++)
		{
			while(j > 0 && pattern[i] != pattern[j])
				j = p[j-1];

			if(pattern[i] == pattern[j])
				p[i] = ++j;
		}
	}

	static ArrayList<Integer> kmp(char[] text, char[] pattern, int[] p)
	{
		int j = 0;

		ArrayList<Integer> position = new ArrayList<>();

		for(int i = 0;i < text.length;i++)
		{
			while(j > 0 && text[i] != pattern[j])
				j = p[j-1];

			//문자가 같은 경우
			if(text[i] == pattern[j])
			{
            	//패턴 매칭 완료
				if(j == pattern.length - 1)
				{
                	//패턴이 나타난 위치들을 저장
					position.add(i - pattern.length + 2);
					j = p[j];
				}
				else
					j++;
			}


		}

		return position;
	}


	public static void main(String[] args) {

		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

			//KMP
			char[] text = br.readLine().toCharArray();
			char[] pattern = br.readLine().toCharArray();

			int p[] = new int[pattern.length];

			failureFunction(p, pattern);
			ArrayList<Integer> position = kmp(text, pattern, p);

			bw.write(position.size()+"\n");
			
			for(int a : position)
				bw.write(a+" ");

			bw.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}

	}
}