백준 5525 - IOIOI

Java

5525 번 - IOIOI

문제

접근 방법

KMP 알고리즘을 사용하여, 주어진 문자열에서 일치하는 패턴의 개수를 세었다.

코드

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

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	m = stoi(br.readLine());

    	char[] str = br.readLine().toCharArray();

    	StringBuilder sb = new StringBuilder();
    	sb.append('I');
    	for(int i = 0; i < n; i++) {
    		sb.append("OI");
    	}

    	char[] pattern = sb.toString().toCharArray();

    	int plen = pattern.length;
    	// 실패함수 만들기
		// i:접미사 포인터(i=1부터 시작: 우리는 실패함수를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.)
		// i는 계속 한칸 씩 증가한다.
		// j:접두사 포인터
		// 만약 현재 j가 가리키는 접두사와 i가 가리키는 접미사가 같으면, i와 j를 동시에 증가시키고
		// 현재 접두사와 접미사가 다르면, j는 실패함수에 따라 뒤로 간다.
    	int[] fail = new int[plen];

    	for(int i = 1, j = 0; i < plen; i++) {
    		while(j > 0 && pattern[i] != pattern[j]) {
    			j = fail[j - 1];
    		}
    		if(pattern[i] == pattern[j])
    			fail[i] = ++j;
    	}

    	int slen = str.length;

    	// 실제 패턴과 문자열 비교, i는 앞으로 한칸 씩만 움직이고, j가 왔다갔다 한다.
    	for(int i = 0, j = 0; i < slen; i++) {
    		while(j > 0 && str[i] != pattern[j])
    			j = fail[j - 1];

    		if(str[i] == pattern[j]) {
    			if(j == plen - 1) {
    				result++;
    				j = fail[j];
    			}
    			else
    				j++;
    		}

    	}

    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

KMP를 자주 복습

개선할 점