JAVA KMP 모드 매 칭 알고리즘 구현

next () 배열 가 져 오기

	/**
	 *   next  
	 * data      
	 * */
	public static int[] getNext(String data){
		int[] next=new int[data.length()] ;
		next [0]=0;
		int index=0;
		for (int i = 1; i < next.length; i++) {
			//               
			index =next[i-1];
			//                            
			if(data.charAt(index)==data.charAt(i)){
				//   ,         +1
				next[i]=index+1;
			}
			else{
				//    ,          
				next[i]=0;
			}
		}
		return next;
	}
	

일치 문자열

/**
	 * str     
	 * date      
	 * */
	public static int find(String str,String data){
		int[] next=getNext(data);
		//      
		int i=0;
		//       
		int j=0;
		//         
		int count=0;
		while(i++<str.length()){
			if(count==data.length()){
				//      
				return i+1-count;
			}
			if(str.charAt(i)==data.charAt(j)){
				j++;
				count++;
			}else{
				//    ,          
				j=next[j];
				count=j+1;
			}
		}
		return -1;
		
	}

테스트 사례

public static void main(String[] args) {
		String res = Arrays.toString(getNext("abcdabd"));
		System.out.println("next   :"+res);
		 int find = find("kajhdabcdabdasdaf","hda");
		 System.out.println("     :"+find);
	}

출력 결과

next   :[0, 0, 0, 0, 1, 2, 0]
     :3