글 읽기 - 시간초과 도와주세요.

hwj0623 2년 전 0

kmp 쓰는데 시간초과가 나네요.

겹쳐서 존재하는걸 찾기 위해 i = pattern.length -2로 돌려서 다시 검색을 하는데, 이 부분이 시간초과가 나는지 잘 모르겠습니다.

--------

질문검색란에 올라온거 다 통과했는데 잘 안되네요.

일본 정올도 테케를 구할 수 있나요?

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

//2
//25
//OOIOIIOIOIOIOIOIOIOIOOIOI

public class Main {
	// d 배열생성
	private static int[] computeTemporaryArray(char pattern[]) {
		int[] lps = new int[pattern.length]; // 가장 긴 패턴 부분문자열 길이 저장 배열
		int index = 0;
		for (int i = 1; i < pattern.length;) {
			if (pattern[i] == pattern[index]) {
				lps[i] = index + 1;
				index++;
				i++;
			} else {
				if (index != 0) {// j!=0이면 보정 가능
					index = lps[index - 1];
				} else {
					lps[i] = 0;
					i++;
				}
			}
		}
		return lps;
	}

	// KMP 알고리즘
	public static int KMP(char[] text, char[] pattern) {
		int ret = 0;
		int lps[] = computeTemporaryArray(pattern);
		int i = 0;
		int j = 0;
		while (i < text.length && j < pattern.length) {
			if (text[i] == pattern[j]) {
				// 발견한 패턴 개수만큼 카운트
				i++;
				j++;
				if (j == pattern.length) {
					ret++;
					j = 0;
					i = i - pattern - 2 ;
					// pattern이 IOIOI고 text에서 이를 찾으면
					// 가운데 I부터 시작해야 한다. 이 시점에서 i 인덱스는 5번인덱스에 위치해 있으므로,
					// -1 후에 길이 절반만큼빼준다.
				}
			} else {
				if (j != 0) {
					j = lps[j - 1];
				} else {
					i++;
				}
			}	
		}
		return ret;
	}

	public static char[] generate(int n) {

		char arr[] = new char[2 * n + 1];
		for (int i = 0; i < arr.length; i++) {
			if (i % 2 != 0) {
				arr[i] = 'O';
			} else {
				arr[i] = 'I';
			}
		}
		return arr;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		char arr[] = generate(N); // pattern string
		String text = br.readLine(); // text string
		int ret = KMP(text.toCharArray(), arr);
		System.out.println(ret);

	}

}

sgchoi5 2년 전 0

http://gooddaytocode.blogspot.... 입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

시간초과 도와주세요.

hwj0623 2년 전 0

sgchoi5 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말