문자열 Hashing에 대하여

Hash는 특정 조건을 만족하는 함수이다.

 

정의역은 굉장히 넓고 그에 비해 치역은 좁다. 그래도 충분히 넓어서 서로 다른 정의역 원소에 대해 함수값이 충돌할 가능성이 적다.

 

치역은 보통 C++에서의 long long 등의 자료 형태로 표현되어 처리하기 간단하다.

 

그렇기 때문에 해시값이 같은 경우 두 대상은 서로 같을 확률이 아주 높다.

 

특히 부분 문자열에 대한 문제에서 많이 사용한다. 부분 문자열끼리 서로 완벽하게 비교하는데 걸리는 시간은 너무 오래 걸린다. 그렇기 때문에 해시값을 통해 비교와 처리를 하는 경우가 많다.

 

 

문자열 Hashing을 사용하는 문제 예시

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

10840번: 구간 성분

부분 문자열의 구성 원소의 순서와 관계없이 성분만 동일하면 같은 것으로 간주하는 문제이다.

 

문자 a부터 z까지 고유 번호를 두어 부분 문자열을 구성하는 구간 안의 고유 번호 합으로써 해시값을 정의하면 된다.

 

해시값이 서로 같더라도 사실은 두 구간이 같지 않은 가능성도 생길 수 있다. 이 경우 두 구간의 길이 또한 같이 비교해주면 훨씬 가능성이 줄어든다.

 

 

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

8228번: A Horrible Poem

처음에 LCP로 도전하다가 TLE가 떠서 좌절했던 문제. 문자열에서 시간이 너무 오래 걸린다 싶으면 해시를 떠올리는 것도 괜찮은 생각이다.

 

구성요소의 순서까지 같아야 서로 같은 부분 문자열이라고 정의하자. 해시 소수값을 하나 두어($p$) $i$번째 문자가 $s_i$이면 $s_i \cdot p^i$ 값을 한 정수 배열에 저장하고, 그 정수 배열의 부분합을 관리한다. 이렇게 두면 modular inverse를 통하여 $[l, r]$ 구간의 부분 문자열의 해시값을 $O(1)$ 만에 구할 수 있다.

 

이 문제의 경우 각 쿼리의 내용을 $[l, r]$이라 했을 때, $hash([l, r-k]) = hash([l+k, r])$를 만족하는 최소 $k>0$를 찾는 문제이다. (단, $k$는 $r-l+1$의 약수이다.)

 

Naive하게 풀면 무조건 TLE다. $[l, r]$ 구간 내에 각 알파벳의 출현 빈도를 계산하자. 만약 문자 'a'가 $n_a$번 출현한다면 $[l, r]$을 균등하게 자를 분할의 개수는 무조건 $n_a$의 약수이다. 이 점을 이용해서 루프 횟수 자체를 아주 줄일 수 있다.

 

 

이 문제처럼 부분 문자열을 hashing 했을 때 일부 Codeforces 고인물들은  hack을 성공하곤 한다.. 애초에 해시 자체가 완벽한 단사함수가 아니라 어쩔 수 없는 문제다.

 

이러한 문제를 피해가기 위해 온라인 대회에서는(즉, 미리 서드파티 코드를 짤 수 있는 대회에서는) 해시 소수 자체를 랜덤하게 뽑아서 쓸 수 있도록 코딩해주면 좋다. 아래는 내가 주로 쓰는 코드이다.

 

class hash_substring {
	typedef long long ll;

	const static int HASH_MAX = 10; // to defense from hack
	const ll HASH_MODS[HASH_MAX] = {1000180033, 1031825407, 1037281769, 1043566169, 1070996533, 1101601643, 1106614007, 1177477843, 1190965717, 1196697457};
	const ll HASH_PRIMES[HASH_MAX] = {100403, 142433, 143779, 183203, 185099, 189583, 220537, 289039, 291869, 295033};

		void make_hash_inv() {
            // 페르마 소정리를 이용한 modular inverse
			ll p = hash_mod - 2, x = hash_prime;
			hash_inv = 1;
			while (p) {
				if (p&1) hash_inv = (hash_inv * x) % hash_mod;
				x = (x * x) % hash_mod;
				p >>= 1;
			}
			assert(hash_inv * hash_prime % hash_mod == 1);
		}

		void make_hash_pows(int n) {
			hash_pows.assign(n+1, 1);
			hash_inv_pows.assign(n+1, 1);

			for (int i=1; i<=n; i++) {
				hash_pows[i] = (hash_pows[i-1] * hash_prime) % hash_mod;
				hash_inv_pows[i] = (hash_inv_pows[i-1] * hash_inv) % hash_mod;
			}
		}

	public:
		ll hash_mod, hash_prime;
		ll hash_inv;
		int size = 0;
		string str;
		vector<ll> sum;
		vector<ll> hash_pows, hash_inv_pows;

		hash_substring() {
			srand(time(0));
			hash_mod = HASH_MODS[rand() % HASH_MAX];
			hash_prime = HASH_PRIMES[rand() % HASH_MAX];
			make_hash_inv();
		}

		hash_substring(hash_substring &hs) {
			hash_mod = hs.hash_mod;
			hash_prime = hs.hash_prime;
			hash_inv = hs.hash_inv;
			make_hash_inv();
			set_string(s);
		}

		void set_string(string &s) {
			int prev_size = size;
			size = s.size()-1;
			sum.assign(size+1, 0);
			if (prev_size < size)
				make_hash_pows(size);
			for (int i=1; i<=size; i++) {
				sum[i] = (sum[i-1] + hash_pows[i] * s[i]) % hash_mod;
			}
		}

		ll hash_value(int l, int r) {
			// from s[l:r] with 1-base
			ll partial = (sum[r] - sum[l-1] + hash_mod) % hash_mod;
			return partial * hash_inv_pows[l] % hash_mod;
		}
};

 

 

https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf

불러오는 중입니다...

COCI 2009/2010 Contest #2 F번 문제. 군대에서 태블릿에서 풀고 테스트데이터 채점 결과는 맞았는데, 백준 온라인 저지에 없는 문제다 ㅠㅠ 군대에서 새벽 4시에 잠 깨고 갑자기 풀이가 떠올라서 태블릿 터치로 낑낑 코딩하고 맞춰서 기분이 아주 좋았다.

 

문제는 간단하다.

 

최대 1000개의 정수 큐가 있다. 각 정수 큐는 최대 1000개의 원소를 초기에 가진다. 각 원소들의 범위는 int 범위이다. 배열 $A$는 초기에 비어있다. 적절한 순서대로 큐를 pop하여 그 원소를 배열 $A$의 마지막 원소로 넣고 싶다. 결과적으로 모든 큐를 텅 비게 만들고, 사전순으로 가장 앞서는 배열 $A$를 만들고 싶다. 그 결과 배열 $A$를 구하여라.

 

적당히 priority_queue로 탐욕적으로 구하면 풀릴 것 같지만 F번 답게 그렇게 쉽지 않다. 예를 들어,

 

Queue1 : 4 3 5 3

Queue2 : 4 3 2 5

Queue3 : 4 3 5 7

 

일 때, 결과 배열은 4 3 2 4 3 4 3 5 3 5 5 7 이다. 큐의 첫 원소만 본다면 Queue2 원소를 우선적으로 빼야한다는 사실은 어떻게 추론할 수 있을까? 조금 더 세밀한 탐욕법이 필요하다는 것을 알 수 있다.

 

큐들의 첫 원소 중 압도적으로 작은 숫자가 있다면 그 숫자를 먼저 pop해야 함은 자명하다. 그렇지 않고 서로 같은 최소 원소들이 있으면 곤란하다.

 

여기서 돌파구가 바로 부분 수열 해싱이다. Queue1, 2, 3을 비교할 때는 공통 부분인 '4 3'을 제외하고 그 다음 원소를 기준으로 비교해서 제일 작은 원소(2)를 가지는 Queue 2를 고르는 것이 가장 합리적이기 때문이다. 두 큐의 최대 prefix 공통부분은 이분탐색으로 찾으면 된다. 그것을 가능케하는 것이 해싱임은 아주 놀랍다.