문자열 검색 전체 알고리즘

package main;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 짚더미 문자열(H)와 바늘문자열(N)이 주어졌을 때,
 * H에 N이 몇번째 자리에서 속하는지 알아내기
 * @param args
 */
public class Main {
	public static void main(String[] args) {
		
		String H = "avava";
		String N = "ava";
		
//		ArrayList<Integer> result = searchNaive(H, N);
		ArrayList<Integer> result = kmpSearch(H, N);
		
		for(Integer begin : result) {
			System.out.println("begin : " + begin);
		}
		
//		ArrayList<Integer> pi = getPartialMatchNaive("aabaabac");
//		pi.forEach(data -> System.out.println("data : " + data));
	}
	
	static ArrayList<Integer> searchNaive(String H, String N) {
		
		ArrayList<Integer> ret = new ArrayList<Integer>();
		
		for(int begin = 0; begin + N.length() <= H.length(); begin++) {
			boolean matched = true;
			
			for(int i = 0; i < N.length(); i++) {
				if(H.charAt(begin + i) != N.charAt(i)) {
					matched = false;
					break;
				}
			}
			if(matched) ret.add(begin);
		}
		
		return ret;
	}
	
	static ArrayList<Integer> kmpSearch(String H, String N) {
		
		ArrayList<Integer> ret = new ArrayList<Integer>();
		int n = H.length();
		int m = N.length();
		ArrayList<Integer> pi = getPartialMatch(N);	// 접두사이면서 접미사인 최대 문자열
		int begin = 0;
		int matched = 0;
		
		while(begin <= n - m) {
			if(matched < m && H.charAt(begin + matched) == N.charAt(matched)) {
				matched++;				
				if(matched == m) ret.add(begin);
			}else {
				if(matched == 0) {
					begin++;
				}else {
					begin += matched - pi.get(matched - 1);
					
					matched = pi.get(matched - 1);
				}
			}
		}
		
		
		return ret;
	}
	
	static ArrayList<Integer> getPartialMatchNaive(String N) {
		
		int m = N.length();
		Integer[] piArr = new Integer[m];
		for(int i = 0; i < piArr.length; i++) {
			piArr[i] = 0;
		}
		ArrayList<Integer> pi;
		
		// 단순한 문자열 검색 알고리즘 구현
		for(int begin = 1; begin < m; begin++) {
			for(int i = 0; i + begin < m; i++) {
				if(N.charAt(begin + i) != N.charAt(i)) break;
				piArr[begin + i] = Math.max(piArr[begin + i], i + 1);
			}
		}
		
		return pi = new ArrayList<Integer>(Arrays.asList(piArr));
	}
	
	static ArrayList<Integer> getPartialMatch(String N) {
		
		int m = N.length();
		Integer[] piArr = new Integer[m];
		for(int i = 0; i < piArr.length; i++) {
			piArr[i] = 0;
		}
		ArrayList<Integer> pi;
		
		int begin = 1;
		int matched = 0;
		
		while(begin + matched < m) {
			if(N.charAt(begin + matched) == N.charAt(matched)) {
				matched++;
				
				piArr[begin + matched - 1] = matched;
			}else {
				if(matched == 0) begin++;
				else {
					begin += matched - piArr[matched - 1];
					matched = piArr[matched - 1];
				}
			}
		}
		
		return pi = new ArrayList<Integer>(Arrays.asList(piArr));
	}
	
	
	
	
}