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년 전
일단 제 풀이는 다음과 같습니다.
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 배열이며 해시 충돌이 일어날 일은 없습니다.