5525번 IOIOI

https://www.acmicpc.net/problem/5525

pattern을 String으로 하면, 시간 초과가 발생한다.

StringBuilder을 사용해야한다.

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
    
    static int N, M;
    
    // table 구축
    static Vector<Integer> makeTable(String pattern) 
    {
        int patternSize = pattern.length();
        
        Vector<Integer> table = new Vector<Integer>();
        
        for(int i=0; i<patternSize; i++) {
            table.add(0);
        }
 
        int j = 0;
        
        /* 일치하는 경우에는 i와 j 둘 다 증가시켜준다.
         * 일치하지 않는 경우에는 i는  증가, j는 현재 table 내에서 (j-1)번 째 인덱스의 값으로 바꿔준다.
         */
        
        for(int i=1; i<patternSize; i++) {
            while(j > 0 && pattern.charAt(i) != pattern.charAt(j))
            {
                j = table.get(j - 1);
            }
            
            if(pattern.charAt(i) == pattern.charAt(j)) {
                table.set(i, ++j);
            }
        }
        
        return table;
    }
    
    /* 매칭이 이루어지지 않는(실패한) 인덱스(index)에서 1을 뺀 인덱스(index - 1)가 가리키는
     * 그 값으로 j를 이동시킨다.
     * i는 계속 앞으로 나아가기만 하면 된다.
     */
    static int kmp(String parent, String pattern)
    {
        Vector<Integer> table = new Vector<Integer>();
        table = makeTable(pattern);
        
        int ret = 0;
        
        int parentSize = parent.length();
        int patternSize = pattern.length();
        
        int j = 0;
        for(int i=0; i<parentSize; i++) {
            while(j > 0 && parent.charAt(i) != pattern.charAt(j)) 
            {
                j = table.get(j - 1);
            }
            
            if(parent.charAt(i) == pattern.charAt(j)) {
                if(j == patternSize - 1) {
                    ++ret;
                    j = table.get(j); // 찾은 뒤에도 점프
                }
                else {
                    ++j;
                }
            }
        }
        
        return ret;
    }
 
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
            
        String parent = br.readLine();
        StringBuilder pattern = new StringBuilder("I");
        
        for(int i=0; i<N; i++) {
            pattern.append("OI");
        }
        
        bw.write(String.valueOf(kmp(parent, pattern.toString()) + "\n"));
 
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second, third;
    
    PQ(int f, int s, int t) {
        this.first = f;
        this.second = s;
        this.third = t;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
            else if(this.second == p.second) {
                if(this.third < p.third) {
                    return -1;
                }
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}