'KMP' 태그의 글 목록

KMP

2017. 11. 19. 10:09

KMP를 사용해서 풀었고,

LinkedList에 idx값을 담아줬다.

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/1786
	* BOJ 백준온라인져지 1786 찾기 풀이
	*/
	public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static int pi[];
	private static int N,M;
	private static String str,pattern;
	static{
	try{
	str = br.readLine();
	pattern = br.readLine();
	}catch(Exception e){

	}
	}
	public static void main(String args[]) {
	initPi(pattern);
	LinkedList<Integer> list = KMP(pattern);
	System.out.println(list.size());
	for(int temp : list){
	System.out.println(temp);
	}
	}
	private static void initPi(String str){
	char[] temp = str.toCharArray();
	pi = new int[temp.length];
	int j = 0;
	for(int i = 1; i<temp.length; i++){
	while (j > 0 && temp[i] != temp[j]) {
	j = pi[j-1];
	}
	if(temp[i] == temp[j]){
	pi[i] = ++j;
	}
	}
	}
	private static LinkedList<Integer> KMP(String s){
	LinkedList<Integer> list = new LinkedList<>();
	int cnt = 0, j = 0;
	char A[] = str.toCharArray(), B[] = s.toCharArray();
	for(int i = 0, length = str.length(); i<length; i++){
	while (j > 0 && A[i] != B[j]){
	j = pi[j-1];
	}
	if (A[i] == B[j]){
	if (j == B.length-1){
	j = pi[j];
	list.add(i-B.length+2);
	}else{
	j++;
	}
	}
	}
	return list;
	}
	}

view raw BOJ_1786.java hosted with ❤ by GitHub

2017. 11. 16. 22:03

가장 큰 거

String을 그대로 사용하면 문자열 추가중에 시간초과가 남

StringBuilder를 사용하면 해결~

KMP는 더 공부가 필요함(PI를 구하는 쪽을 걍 넘어간듯)

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/5525
	* BOJ 백준온라인져지 5525 IOIOI 풀이
	* 이슈 : StringBuilder를 사용하지 않으면 시간초과가 난다.
	*/
	public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static int pi[];
	private static int N,M;
	private static String str;
	static{
	try{
	N = lineToInt();
	M = lineToInt();
	str = br.readLine();
	}catch(Exception e){

	}
	}
	public static void main(String args[]) {
	StringBuilder s = new StringBuilder("I");
	for(int i = 0; i<N; i++){
	s.append("OI");
	}
	initPi(s.toString());
	System.out.println(KMP(s.toString()));
	}
	private static void initPi(String str){
	char[] temp = str.toCharArray();
	pi = new int[M];
	int j = 0;
	for(int i = 1; i<temp.length; i++){
	while (j > 0 && temp[i] != temp[j]) {
	j = pi[j-1];
	}
	if(temp[i] == temp[j]){
	pi[i] = ++j;
	}
	}
	}
	private static int KMP(String s){
	int cnt = 0, j = 0;
	char A[] = str.toCharArray(), B[] = s.toCharArray();
	for(int i = 0; i<M; i++){
	while (j > 0 && A[i] != B[j]){
	j = pi[j-1];
	}
	if (A[i] == B[j]){
	if (j == B.length-1){
	j = pi[j];
	cnt++;
	}else{
	j++;
	}
	}
	}
	return cnt;
	}
	private static int lineToInt() throws IOException{
	return Integer.parseInt(br.readLine());
	}
	}

view raw BOJ_5525.java hosted with ❤ by GitHub

PREV 1 NEXT

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`