[백준] 1786번 : 찾기(JAVA)

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

1786번: 찾기

풀이

기존 KMP알고리즘에서 달라진 부분은 같은 부분이 나올때 count를 세주고 위치를 저장해서 마지막에 출력해주는 부분입니다.

ArrayList를 통하여 위치를 저장해주고 count를 선언하여 ++해줍니다(전역)

여기서 StringBuilder를 써주냐 안써주냐의 차이로 시간이 2500ms 가량이 차이납니다(확실 x)

 

소스코드

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

public class Main {
	static int count = 0;
	static ArrayList<Integer> arr = new ArrayList<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

		KMP(br.readLine(), br.readLine());
		
		StringBuilder sb = new StringBuilder();
		sb.append(count).append("\n");
		for(int n : arr) {
			sb.append(n).append(" ");
		}
		System.out.print(sb);
	}
	
	public static int[] getpi(String s1) {
		int[] pi = new int[s1.length()];
		int j = 0;
		for(int i = 1; i < s1.length(); i++) {
			while(j > 0 && s1.charAt(i) != s1.charAt(j)) {
				j = pi[j - 1];
			}
			if(s1.charAt(i) == s1.charAt(j)) {
				pi[i] = j += 1;
			}
		}
		return pi;
	}
	
	public static void KMP(String s, String s1) {
		int[] pi = getpi(s1);
		int j = 0;
		for(int i = 0; i < s.length(); i++) {
			while(j > 0 && s.charAt(i) != s1.charAt(j)) {
				j = pi[j - 1];
			}
			if(s.charAt(i) == s1.charAt(j)) {
				if(j == s1.length() - 1) {
					count++;
					arr.add(i - j + 1);
					j = pi[j];
				}
				else {
					j++;
				}
			}
		}
	}
}