gs25   1년 전

일단 제 풀이는 다음과 같습니다. 

a를 지우는 길이 b를 늘리는 길이라 했을때, b는 T의 suffix로 고정되니까 S-a+b 가 그래프에 속하는지 해싱으로 체크하고 b<=a 일때 S[|S|-2a+b] 길이 (s의 prefix) 가 lcp(S,T) 이하인지 체크, b>a 일 때 T[|S|-a+1:|S|+b-2a] = T[|S|+b-2a+1:|S|+2b-3a] 와 |S|-a <= lcp(s,t) 인지 체크

입니다. 우선 해당 풀이로 ac를 받은 상태입니다. 

틀린 부분이 112번째 줄에서 그래프의 모든 해시값안에 S-a+b 의 해시가 속하는지 체크하는 파트가 잘못된 것 입니다. 이걸 나이브하게 체크하는 방식으로 할때 ac를 받았습니다. 왜 S-a+b의 해시가 속하는데 실제 S-a+b 가 (해당 문자열은 S[:|S|-a]+T[-b:] 로 해석하면 됩니다. S의 prefix + T의 suffix) 그래프에 속하지 않을 수 있는지 궁금합니다. 주의 깊게 봐야할 부분은 pf, sf 배열이며 해시 충돌이 일어날 일은 없습니다. 

gs25   1년 전

94번줄 for(int i=u;i>=u-t_string.size()+1&&i>=0;i--){ 
에서 size_t 형변환으로 오버플로우가 나네요 ㅠㅠ  

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