cocobo123   2년 전

안녕하세요?

이번 찾기 문제를 라빈 카프로 풀려다가 계속 시간초과가 발생해서 궁리해봤더니

찾으려는 pattern이 길이가 너무 길면 해시값이 맞아도 해시값이 맞는지 strcmp 할 때 시간으로 시간초과가 나지 않을까라는 생각이 들었습니다.

그렇다고 strcmp를 하지 않고 해시값만으로 pattern 일치여부를 했더니 틀렸다고 나옵니다.

제가 코드를 잘못 짰을 가능성두 있을거 같네요.

첨언 부탁드립니다.

djm03178   2년 전

100만자리에서 10억7의 모듈로는 충돌 확률이 매우 높지 않을까 생각합니다.

cocobo123   2년 전

감사합니다.

그러면 strcmp가 반드시 필요한 사항이잖아요?

그런데 strcmp를 했을 경우에는 시간초과가 발생합니다.

본문 : aaaaaaaaa ...aaaaaaa

패턴 : aaaaaaaaa...aaaaa 

처럼 일 때 아무래도 계속 strcmp를 해서 시간이 초과된다고 짐작합니다만

혹시 개선방법이 있을까요?

djm03178   2년 전

mod 10억7 말고 훨씬 큰 수로 하면 됩니다. long long 범위 전체를 사용한다면. 해시 함수만 잘 만들면 사실상 충돌이 없다고 볼 수 있습니다.

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