peter3343   1년 전

kmp 알고리즘을 써서 풀었는데 시간초과가 납니다. 틀린 부분이 어디에 있나요?

ppp123   1년 전

31번째 줄 j = kmp[j]; -> 이게 잘못됐네요 (j = kmp[j-1] 로 변경해보세요)

kmp 배열은 lps 를 담고 있습니다. (접두사 == 접미사의 최대 일치 값)


계속 패턴이 매칭해가며, 연승을 하다가 j에서 끊긴 상황이라, 현재 j의 lps가 아니라 j-1의 lps를 확인해야합니다.

그래야 이전의 lps기반으로 접두사를 접미사로 옮겨 문자열을 재사용할 수 있겠지요.

해당라인에서 kmp[j]는 확정되지 않은 값이라 의미가 없는 값입니다.

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