[JAVA] kmp알고리즘

 

kmp알고리즘

package kmp;

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

public class Main {
	static int[] table; //"주문" [0, 0]
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	String s = br.readLine(); //안녕하세요주문할게요
    	String p = br.readLine(); //주문
    	
    	makeTable(p); //테이블값생성 // 접두사도 되고 접미사도 되는 문자열의 최대 길이 구해서 table에 배열로 넣음 //"주문" 들어갈때 결과 : table[] 0 0
    	
    	System.out.println(search(s, p)); //[]
    }
    
    public static int search(String str, String pattern) {
    	int sLen = str.length(); //안녕하세요주문할게요 11
    	int pLen = pattern.length(); //주문 2
    	 
    	int index = 0;
    	for(int i = 0; i < sLen; i++) { //i가 0이고, 0<11, i++
    		while(index > 0 && str.charAt(i) != pattern.charAt(index)) { //1>0 이고, "안녕하세요주문할게요"의 1번째인 "녕" 과 "주문"의 1번째인 "문"가 같지않을때
    			index = table[index - 1];  //index가 1이고 "문" (두번째조회가시작되고 글자가 안맞으면) "주문"table[0, 0]의 1은 "문"이니까 1-1 이면 0으로 "주"로 비교
    		}
    		
    		if(str.charAt(i) == pattern.charAt(index)) { //글자가 대응될경우
    			
    			if(index == pLen - 1) { //index값이 ("주문"문자열 길이-1) 1까지 도달했다면 문자열 매칭을 성공한 것이므로 탐색을 종료한다. 
    				index = table[index];
    				return 1;
    			}
    			else {
    				index++; //"주"만 찾았다면 "문"을찾아야되니 index++
    			}
    		}
    	}
    	return 0;
    }
    
    public static void makeTable(String pattern) { //"주문"
		int pLen = pattern.length(); //2 
		table = new int[pLen]; //table 2로생성
		
		int index = 0;
		for(int i = 1; i < pLen; i++) { //i는1부터시작 , 1<2; , i++ // 한바퀴돌고 i가 2가 되고 끝남
			while(index > 0 && pattern.charAt(i) != pattern.charAt(index)) { //index 0>0 이고, "주문"의 1번째 "문" != "주문"의 0번째 "주" 으면 
				index = table[index - 1]; 
			}
			
			if(pattern.charAt(i) == pattern.charAt(index)) { //"주문"의 1번째 "문" == "주문"의 0번째 "주"
				index += 1;
				table[i] = index;  
			}
		}
 	}
}

코드출처 : https://hanyeop.tistory.com/355
https://www.acmicpc.net/problem/16916

설명참고하기 : https://loosie.tistory.com/192

[알고리즘] 문자열 매칭 알고리즘 KMP (Java)

---

 

응용 코드

문장이 주어졌을때, intendMap의 key와 동일한 키워드를 찾, 그에 맞는 value인 의도를 찾아 출력한다.

package kmp;

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Main {
	static int[] table; //"주문" [0, 0] 

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

		String s = "안녕하세요.주문할게요."; // 전체문자열 (문장)
		// String p = br.readLine(); //비교할부분문자열 (키워드)

		Map<String, Object> intendMap = new HashMap<String, Object>();
		intendMap.put("주문", "음식주문");
		intendMap.put("배달", "배달주문");

		for (Map.Entry<String, Object> entry : intendMap.entrySet()) {
			String p = entry.getKey();

			makeTable(p); // 키워드전달

			// search함수에 문장과 키워드를 넣었을때 결과
			String findkey = search(s, p); // findkey: 주문,계산,결제

			// 찾은키워드랑, intendMap이가지고있던 키워드랑 동일할때
			if (findkey.equals(p)) {
				// intendMap에서 key로 findkey를 가지고있을때
				if (intendMap.containsKey(findkey)) {
					Object findValue = intendMap.get(findkey);
					System.out.println("찾은키워드 :" + findkey + " 찾은의도: " + findValue); //"getIntend": {"txt": "배달주문하겠습니다.", "주문": "음식주문","배달": "배달주문"}
				} else {
					System.out.println("일치하는 의도가 없습니다.");
				}
			}

		}
	}

	public static String search(String str, String pattern) {
		int sLen = str.length(); //안녕하세요주문할게요 11
		int pLen = pattern.length(); //주문 2

		String foundPattern = ""; // 반환할 키워드 담을곳

		int index = 0;
		for (int i = 0; i < sLen; i++) { //i가 0이고, 0<11, i++
        	// index번 글자와 짚더미의 해당 글자가 불일치할 경우, 
			// 현재 대응된 글자의 수를 table[index-1]번으로 줄인다
			while (index > 0 && str.charAt(i) != pattern.charAt(index)) { //1>0 이고, "안녕하세요주문할게요"의 1번째인 "녕" 과 "주문"의 1번째인 "문"가 같지않을때
				index = table[index - 1]; //index가 1이고 "문" (두번째조회가시작되고 글자가 안맞으면) "주문"table[0, 0]의 1은 "문"이니까 1-1 이면 0으로 "주"로 비교
			}

			if (str.charAt(i) == pattern.charAt(index)) { //글자가 대응될경우

				if (index == pLen - 1) { //index값이 ("주문"문자열 길이-1) 1까지 도달했다면 문자열 매칭을 성공한 것이므로 탐색을 종료한다. 
					index = table[index];
					foundPattern = pattern; // 키워드 담기
					break;
				} else {
					index++; //"주"만 찾았다면 "문"을찾아야되니 index++
				}
			}
		}

		return foundPattern; // 찾은 키워드 반환하기
	}

	// 의도전달받음 //접두사와 접미사가 일치하는 최대길이를 구한 부분 일치 테이블
	public static void makeTable(String pattern) { //"주문"
		int pLen = pattern.length(); // 키워드 길이 "주문"-2
		table = new int[pLen];  //table 2로생성

		int index = 0;
		for (int i = 1; i < pLen; i++) { //i는1부터시작 , 1<2; , i++ // 한바퀴돌고 i가 2가 되고 끝남
			// 일치하는 문자가 발생했을 때(index>0), 연속적으로 더 일치하지 않으면 index = table[index - 1]; 로 돌려준다.
			while (index > 0 && pattern.charAt(i) != pattern.charAt(index)) {  //index 0>0 이고, "주문"의 1번째 "문" != "주문"의 0번째 "주" 으면 
				index = table[index - 1];
			}

			if (pattern.charAt(i) == pattern.charAt(index)) { //"주문"의 1번째 "문" == "주문"의 0번째 "주"
				index += 1;
				table[i] = index;
			}
		}
	}
}