[일반] 라빈카프질문점

[pppppp(219.248)]

https://www.acmicpc.net/problem/3033

이거 라빈카프로 푸는 문제라는데 입력 데이터가

aaaaaaaaaaaa... 같이 들어오면

단순비교하다가 시간초과 나는거 아님?

라빈카프 쓸 때 해싱값이 같으면 충돌고려해서 완탐 안하고 바로 같은 문자열로 취급함?

- dc official App

[익명(223.38)]

전 그렇게함

[pppppp(219.248)]

충돌 발생해서 답이 없는데 있는걸로 판단하면 어떡함? 해시값 구할 때 x값 2개로 구하는 식으로 충돌을 막음? - dc App

[익명(223.38)]

그런식으로 충돌확률 줄이고 저격데이터 없길 바라야죠

[pppppp(219.248)]

수학적으로 완벽하지 않은 알고리즘이 쓰이고 그런데도 이걸로만 풀리는 문제가 나온다는게 신기하네 - dc App

[익명(223.38)]

그걸로만 풀리는 문제라고 누가그럼?

[pppppp(219.248)]

라빈카프로만 풀리는 문제같은건 존재 안함? 이 문제가 그렇다는게 아니라 - dc App

[pppppp(219.248)]

그런문제가 존재 안하면 라빈 카프는 뭔가 그냥 꼼수 같은 느낌인데 - dc App

[익명(121.131)]

해싱이라는게 0~mod-1 까지 고르게 매핑한다고 가정하고 쓰는거고 충돌날 확률이라는걸 계산했을때 충분히 작다고 생각되면 쓰는거지

[익명(223.38)]

저건 완전탐색으로 하되 같은 값 나오자마자 나가는 방식으로 써도 되긴 함

[익명(223.38)]

연결 리스트에 해시별 위치 저장해두고 같은 해시의 위치들에 대해서만 문자열도 같은지 확인 -> 같은거 나오면 있다고 보고 종료 저 문제 정해가 저런 방법 쓰더라. 저격 데이터가 아닌 이상 해시가 같지만 다른 문자열이 많이 쌓일 가능성이 희박하다는걸 이용한거

[pppppp(219.248)]

해시값은 같은데 다른 문자열인 위치가 여러개인 경우는 거의 없긴 하겠네 - dc App

[캐티(tae826)]

기본적으로 ps에서 해시로 푸는 문제는 꼼수 같은 느낌이 맞긴 함. 실제로 코포 같은 데서는 해시 한 번 잘못 쓰면 저격데이터 기가 막히게 잘 만드는 누텔라들한테 코드 해킹당함

[pppppp(219.248)]

해시값 여러개 묶어서 하나의 키로 관리해도 저격당할 수 있나 핵데이터는 어케만드는겨 ㄷㄷ - dc App

[캐티(tae826)]

그렇다고 랜덤을 쓰는 풀이가 다 꼼수라는건 아니긴 함 ㅇㅇ. 실제로도 랜덤을 사용하는 알고리즘도 많고 랜덤을 썼을때 시간 복잡도가 달라지는 문제들도 잇는걸로 암

[pppppp(219.248)]

랜덤으로 푸는 문제들은 확률적으로 그냥 틀릴 확률이 로또맞을 확률이니까 이해가 가는데 해싱은 임의로 저격데이터를 만들 수 있으니까 걍 거부감이 든다 문자열 죽어 ㅠㅠ - dc App

[캐티(tae826)]

뭐 일반적인 경우에서 해시가 충돌할 확률은 다른 랜덤 문제들이랑 비슷하게 낮을거임 ㅇㅇ. 찝찝할 순 있어도 그런 식으로 데이터 뚫는 것도 PS/CP의 매력이라고 생각함