우선 작정하고

aaaaaa...aaaa 

aaa...aaa

이런 종류의 예제가 들어오면 시간초과가 발생하는 코드입니다.

해시값이 같을때마다 비교를 한번 더 하시는데

저런식으로 모든 구간의 패턴이 전부 일치하면 전부 비교하게 되어 시간초과가 발생합니다.

그리고 1e18 + 7 은 해시 범위가 너무 커서 계산 도중 오버플로우가 발생하여 실제값과 달라져서 틀린 것 같습니다.

감사합니다!!!

@shjgkwo 혹시 하나만 더 여쭤봐도 될까요?

해시값이 같을때마다 비교하는 부분을 없애고

각 문자마다 곱하는 x의 지수승에서 x의 값을 2에서 다른값으로 바꿨는데

7로만 바꿔줘도 되더라구요. 그말은 즉 x를 7로 잡으면 해쉬값이 같으면서 서로 다른 문자열이 없다는 말인것 같은데

이건 이 문제의 데이터에 한해서만 돌아가는 소스코드 일까요...?

아뇨 정확히는 해시과정에서 해시 충돌이 발생할 확률이 극단적으로 작은것을 이용한 방법입니다.

우선 생각해두어야 할것이, 데이터라는것이 채점을 위해서 한정적으로 존재할 수 밖에 없으며

라빈카프를 구현 방법에 따라 오만가지 모듈러 값이 존재할 수 있고, 곱해주는 수도 다를 수 있습니다.

실제 상황에서 그런 모든 코드를 카운터 치는 테스트 케이스를 만드는 것을 굉장히 어렵습니다.

그래서 이론적으로는 질문 작성자님이 작성하신 코드처럼 한번 검사하는 것이 맞는 방법입니다.

하지만 속도를 위해서, 해시충돌이 일어나지 않을것이라 가정하고(확률적으로 적고, 내 코드의 코너 케이스를 못만들것이란 기도메타) 검사하지 않고 코드를 제출하는것입니다.

이 문제에 한해서 돌아간다기 보다는 위에 언급처럼 해시충돌이 일어나도록 유도하는 테스트 케이스가 만들기 힘든것을 이용한것입니다.

대회에서 사용하는 테크닉과, 실제 이론은 상이하다는 점만 기억해주시면 되겠습니다.

잘 알겠습니다. 감사합니다!!