[백준 1786] 찾기

[백준 1786 : 찾기 ]

문자열 T에서 문자열P를 찾는 문제다..
이 문제는 올해 초 해쉬라는 자료구조를 배우고 문자열 문제들을 풀었는데
100만 이하 문자열이니 기본 문자열 찾는 풀이는 당연히 시간초과가 난다.

전에 틀렸을때는 해쉬와 라빈카프(Rabin-Karp)알고리즘을 이용했었는데
현재 틀린 페이지가 2장이 넘는다... 시간초과 + 틀렸습니다 + 컴파일에러

라빈 카프 알고리즘은 이렇다.

이렇게 한 칸 건너뛸때마다 문자열의 시작부분을 뺀다. 그리고 정한 숫자를 곱한다.
건너뛰어서 더해지는 부분을 더한다.

엄청 간단!!!!

이런식으로 가면 O(T문자열 길이)의 시간복잡도를 가진다.
하지만 NUMBER1_i와 NUMBER2가 일치하더라도 문자열들이 유일한 값을 가지지는 않을 것이다.
그래서 결국 비교하는 시간도 곱해지게된다.
O(T문자열 길이 * 해시값같을때마다 P문자열 길이)

라빈 카프로 푸는데 계속 시간초과 또는 틀렸습니다가 떴다.
초반에 틀린이유는 해싱하면서 int 범위를 넘어갈때 -값으로 되는 것이었고
long long으로 바꾸니 해결됐다.

그래도 시간초과가 계속 났는데 나는 저 해싱값이 유일하다고 정의하지 않았다.
NUMBER1_i == NUMBER2 일때 chk함수로 문자열을 비교했는데
chk함수를 없애니까 해결되었다.
입력데이터가 추가되어야 될 것 같다. 원래는 틀렸습니다가 떠야될듯.

이 문제 때문에 KMP알고리즘 오늘 공부하게 되었는데 따로 글을 게시하며
다시 공부해봐야겠다.