알고리즘/문자열
2020. 8. 5.
해싱
두 문자열이 같은 문자열인지 확인하려고 합니다. 물론 두 문자열의 길이만큼 직접 비교하는 식으로 확인할 수 있지만, 두 문자열의 해시값이 같은지 확인하는 방식으로도 확인할 수 있습니다. 해시 함수에는 다양한 종류가 있지만, 이 문제에 나오는 해시 함수를 이용합니다. https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정� www.acmicpc.net 라빈-카프 알고리즘(Rabin-Karp Algorithm) 어떤 문자열 \(S\)가 주어졌을 때, 이 문자열의 일정한 \(L\)길..