imds39   4년 전

50%대에서 시간초과에러가 발생하는데.. 어디서 시간을 줄여야 하는건지 잘 모르겠습니다! 도와주세요!

일단, KMP랑 비슷하게 INDEX, COUNT 배열을 두었습니다.


INDEX 배열에는 패턴이 Sequential하게 오는 최대길이를 저장합니다.

다음에 i길이 text에서 s길이 패턴을 검사할때 이 값을 이용하여 건너뜁니다.


 COUNT 배열에는 패턴이 Sequential하게 올 때, 그 갯수(주기)를 저장합니다. 

다음에 i길이 text에서 s길이 패턴을 검사할때 INDEX 배열을 이용하여 비교인덱스를 건너뛰게 되는데 그만큼 COUNT도 증가해야 하기 떄문입니다. 


이런식으로 하면 비교하는 횟수를 줄일 수 있다고 생각했는데, 이게 전혀 틀린건지, 아니면 뭔가 빼먹은 부분이 있는지 궁금합니다!

sgchoi5   4년 전

seerc 문제는 대회에서 사용했던 TC 가 공개되어 있으니 한 번 써보세요..

http://gooddaytocode.blogspot....

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