문자열 Hashing에 대하여
Hash는 특정 조건을 만족하는 함수이다. 정의역은 굉장히 넓고 그에 비해 치역은 좁다. 그래도 충분히 넓어서 서로 다른 정의역 원소에 대해 함수값이 충돌할 가능성이 적다. 치역은 보통 C++에서의 long long 등의 자료 형태로 표현되어 처리하기 간단하다. 그렇기 때문에 해시값이 같은 경우 두 대상은 서로 같을 확률이 아주 높다. 특히 부분 문자열에 대한 문제에서 많이 사용한다. 부분 문자열끼리 서로 완벽하게 비교하는데 걸리는 시간은 너무 오래 걸린다. 그렇기 때문에 해시값을 통해 비교와 처리를 하는 경우가 많다. 문자열 Hashing을 사용하는 문제 예시 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로..
