해싱

Error

시퀀스의 해시를 계산하는 대신 각 접두사에 값을 저장할 수 있습니다. 해당 접두사와 동일한 시퀀스의 해시 값이 됩니다.

이러한 구조를 사용하면 이 시퀀스의 하위 세그먼트에 대한 해시 값을 빠르게 계산할 수 있습니다(접두사 합계와 유사).

하위 세그먼트 [l;r]의 해시를 계산하려면 접두사 r에 대한 해시를 가져와 r-l+1의 거듭제곱에 p를 곱한 접두사 l-1에 대한 해시를 빼야 합니다. 접두사에 값을 쓰고 무슨 일이 일어나는지 보면 이것이 왜 그렇게 분명해집니다. 이 사진을 보고 성공하시길 바랍니다.



이러한 작업의 결과로 원래 시퀀스의 하위 세그먼트에 대한 해시를 얻습니다. 또한 이 해시는 이 하위 세그먼트와 동일한 시퀀스의 해시로 간주되는 경우의 해시와 동일합니다(다른 값과 비교하기 위해 각도 등의 추가 변환이 필요하지 않음).

여기서 명확히 해야 할 두 가지 사항이 있습니다.
1) p에 r-l+1의 거듭제곱을 빠르게 곱하려면 p modulo mod의 가능한 모든 거듭제곱을 미리 계산해야 합니다.
2) 우리는 모든 계산을 modulo modulo로 수행하므로 접두사 해시를 뺀 후 음수를 얻을 수 있음을 기억해야 합니다. 이를 방지하기 위해 빼기 전에 항상 mod를 추가할 수 있습니다. 또한 곱셈과 모든 덧셈 후에 모듈로 값을 취하는 것을 잊지 마십시오.

코드에서는 다음과 같습니다.
  #include <bits/stdc++.h> 네임스페이스 표준 사용; typedef 긴 longll; const int MAXN = 1000003; // 기본 및 해시 모듈 llp, 모드; // 접두어 해시와 지수 p h[MAXN], pows[MAXN]; // 하위 세그먼트 [l;r]의 해시 계산 ll get_segment_hash(int l, int r) { return (h[r] + mod - h[l - 1] * pows[r - l + 1] % 모드) % 모드; } 정수 메인() { // 어떻게든 p와 mod를 얻습니다. // 거듭제곱 p를 미리 계산 pows[0] = 1; for (int i = 0; i < MAXN; i++) pows[i] = (pows[i - 1] * p) % mod; // // 주요 문제 해결 // 0을 반환합니다. }

문자열 A의 해시가 h_A 이고 문자열 B의 해시가 h_B인 경우 문자열 AB의 해시를 빠르게 계산할 수 있습니다.
h_AB = h_A * p^|B| + h_B   <- 모듈로 모든 것을 계산
여기서 |비| - 문자열 B의 길이

시퀀스 외에도 세트를 해시할 수도 있습니다. 즉, 순서가 없는 개체 집합입니다. 다음 공식에 따라 계산됩니다.
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- 모듈로 모든 것을 계산
여기서 ord는 가능한 모든 객체 중에서 집합의 객체에 절대 서수를 할당하는 함수입니다(예를 들어 객체가 자연수이면 ord(x) = x이고 소문자 라틴 문자이면 ord(& #39;a') = 1, ord('b') = 2 등)

즉, 각 개체에 대해 기본과 같은 값을 이 개체 수의 거듭제곱에 연결하고 전체 세트의 해시를 얻기 위해 이러한 모든 값을 합산합니다. 수식에서 알 수 있듯이 집합에 요소를 추가하거나 제거하면(필요한 값을 더하거나 빼기만 하면) 해시가 쉽게 다시 계산됩니다. 같은 논리,  단일 요소가 추가되거나 제거되지 않고 다른 집합이 있는 경우(그냥 해시를 더하거나 뺍니다).

이미 이해할 수 있듯이 단일 요소는 해시를 계산할 수 있는 크기 1의 집합으로 간주됩니다. 그리고 더 큰 세트는 단순히 이러한 단일 세트의 합집합이며 세트를 결합하여 해시를 추가합니다.

사실 이것은 여전히 ​​동일한 다항식 해시이지만 p^m 의 계수 이전에는 다음 값을 가졌습니다. 번호 n - m - 1(여기서 n은 시퀀스의 길이) 아래의 시퀀스 요소의 수이며, 이제 이것은 절대 서수가 m과 같은 세트의 요소 수입니다.

그러한 해싱에서는 충분히 큰 기준(최대 세트 크기보다 큼)을 취하거나 이중 해싱을 사용하여 절대 서수 m을 가진 p개 객체 집합이 절대 서수를 가진 하나의 객체가 있는 집합과 동일한 해시를 갖는 상황을 피해야 합니다. 서수 m+1.
 

루트 트리를 효율적으로 해시하는 방법에는 여러 가지가 있습니다. 
이러한 방법 중 하나는 다음과 같이 구성됩니다.
깊이 순회 순서대로 정점을 재귀적으로 처리합니다. 단일 정점의 해시가 p와 같다고 가정합니다. 자식이 있는 정점의 경우 먼저 알고리즘을 실행한 다음 자식을 통해 현재 하위 트리의 해시를 계산합니다. 이렇게 하려면 자식 하위 트리의 해시를 숫자 시퀀스로 간주하고 이 시퀀스에서 해시를 계산합니다. 이것은 현재 하위 트리의 해시가 됩니다.
하위 항목의 순서가 중요하지 않은 경우 해시를 계산하기 전에 하위 하위 트리에서 해시 시퀀스를 정렬한 다음 정렬된 시퀀스에서 해시를 계산합니다.

이렇게 하면 트리의 동형을 확인할 수 있습니다. 자식에 대한 순서 없이 해시를 계산합니다(즉, 자식의 해시를 정렬할 때마다). 그리고 루트의 해시가 일치하면 트리는 동형이고 그렇지 않으면 그렇지 않습니다.

루트가 없는 트리의 경우 모든 것이 비슷한 방식으로 발생하지만 중심을 루트로 가져와야 합니다. 또는 두 개의 중심이 있는 경우 한 쌍의 해시를 고려하십시오.