(알고스팟) 말버릇
*문자열에서 K번이상 등장하는 부분 문자열을 말버릇이라고 한다.
-->해결방법은 접미사배열을 만든 후, 접미사배열의 각 접미사들은 접두사로 만들어 부분문자열을 만들 수있다. 어차피 중복되는 부분문자열을 접미사배열에서 인접해 있기 때문에
각 A[i]와 A[i+k-1]의 가장 긴 길이를 구하며 그것이 k개 이상의 공통부분문자열이 된다.
-->해결방법은 접미사배열을 만든 후, 접미사배열의 각 접미사들은 접두사로 만들어 부분문자열을 만들 수있다. 어차피 중복되는 부분문자열을 접미사배열에서 인접해 있기 때문에
각 A[i]와 A[i+k-1]의 가장 긴 길이를 구하며 그것이 k개 이상의 공통부분문자열이 된다.
댓글
댓글 쓰기