글 읽기 - 시간초과 질문

min0418 7년 전 0

안녕하세요.

예제는 잘 맞는데..오류도 없다고 생각되구요.

시간 초과가 나는데, 어느 경우인지 모르겠네요..

고수님들 도움 부탁 드립니다...

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

 public static void main(String[] args) throws Exception {
  // TODO Auto-generated method stub
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  //BufferedReader br = new BufferedReader(new FileReader("c:/sample_input.txt"));
  
  //StringTokenizer st = new StringTokenizer(br.readLine());
  
  String s = br.readLine();
  String p = br.readLine();
  
  int[] pi = new int[p.length()];

  int m = (int)p.length();
  int j=0;
  ArrayList<Integer> ans = new ArrayList<Integer>();
  
  //Pi 값 찾기 prefix, suffix 에서 서로 같은 최대 길이를 찾음.  
  for(int i=1; i < m; i++)
  {
   while(j > 0 && p.charAt(i) != p.charAt(j))
    j = pi[j-1];
   if(p.charAt(i) == p.charAt(j))
    pi[i]= ++j;
  }
  
  // KMP 시작
  int n= s.length();
  j=0;
  for(int i=0; i < n; i++)
  {
   while(j > 0 && s.charAt(i) != p.charAt(j) )
    j = pi[j-1];
   if(s.charAt(i) == p.charAt(j))
   {
    if(j==m-1)
    {
     ans.add(i-m+2);
     j=pi[j];
    }else
    {
     j++;
    }
   }
  }
  
  System.out.println(ans.size());
  for(int i=0; i < ans.size(); i++)
  {
   System.out.println(ans.get(i));
  }
 }

}

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

문제

문제

출처

ICPC

시간초과 질문

min0418 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말