04.10 학습&숙제

---

문자열 패턴 매칭

긴 문자열에서 특정 문자열을 찾아보자

패턴 매칭에 사용되는 알고리즘

완전탐색, 라빈-카프 알고리즘, 보이어-무어 알고리즘, KMP 알고리즘

---

KMP 알고리즘

맨 앞부터 해당 인덱스까지의 길이가 2이상인 부분 문자열 중 접두사이면서 접미사인 최대 문자열

---

KMP 코드

// 패턴 등장 횟수, 위치를 구하기 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class KMP {
	public static void main(String[] args) throws IOException {
		BufferedReader 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; // j위치까지 일치한 경우 길이는 j+1, 후에 j 뒤로 이동
			}else {
				pi[i] = 0; // 일치하는 접두사 접미사 없음
			}
		}
		
		System.out.println(Arrays.toString(pi));
		
		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		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);
		}
	}
}

---

숙제

기업분석, 금융IT 조사, 정처기 실기 정리