KMP

KMP 베이스 코드

 

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

// 본문에서 패턴이 몇 번 등장하는지 횟수와 등장한 위치들 출력
public class KMP {
	static BufferedReader br;
	static StringTokenizer st;
	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		char[] text = br.readLine().toCharArray();
		char[] pattern = br.readLine().toCharArray();
		int tLength = text.length;
		int pLength = pattern.length;
		
		int []pi = new int[pLength]; // 부분 일치 테이블(실패 함수)만들기 : 패턴 불일치가 발생할 경우 활용해서 패턴 포인터 이동 목적
		
		for(int i=1, j=0; i < pLength; i++) { // 패턴에서 패턴을 찾는 원리 이용
			// i: 패턴의 접미사, j: 패턴의 접두사
			// 두 포인터 위치에서 불일치가 발생하면 맞은 위치의 정보를 활용해서 불필요한 비교를 줄임
			while(j>0 && pattern[i] != pattern[j]) {
				j = pi[j-1]; 
			}
			
			// 현재 i위치까지의 부분문자열의 접미사가 접두사와 일치하는 패턴의 최장길이 저장
			if(pattern[i] == pattern[j]) {
				pi[i] = j+1; // j위치까지 일치하는 경우 길이는 j+1, 후에 j 뒤로 이동 
				j++;
			} else {
				pi[i] = 0; // 일치하는 접두사 접미사 없음
			}
		}
		
		System.out.println(Arrays.toString(pi));
		
		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i=0, j=0; i < tLength; i++) {
			while(j>0 && text[i] != pattern[j]) {
				j = pi[j-1];
			}
			
			if(text[i] == pattern[j]) {
				if(j == pLength-1) { // 일치가 발생한 위치가 패턴의 끝이면
					++cnt; // 패턴 찾았으므로 카운트 증가
					list.add(i-j);
					j = pi[j];
				} else {
					j++;
				}
			}
		}
		
		System.out.println(cnt);
		if(cnt>0) {
			System.out.println(list);
		}
		
	}
}



//ababababcababaca
//ababaca
// 
//==>
//1
//[9]
//
//aaaaaab
//aaa
//
//==>
//4
//[0, 1, 2, 3]
//
//ababababcababaca
//abacabab
//
//==>
//0