# String Hashing
Tham khảo cách cài hash nhiều mod: https://pastebin.com/mE9jbca0
## Mục đích
Biến một xâu ký tự thành một con số ($mod$ $10^9+7$).
Hai xâu bằng nhau $\Rightarrow$ hai số bằng nhau (điều ngược lại chưa hẳn đúng)

## Cách cài đặt:
### Bước 0
Chọn hệ cơ số. Chọn số nguyên tố lớn hơn số "chữ số".
Ví dụ: $base = 257, 311$.
### Bước 1
Xây dựng mảng các giá trị $base^k$ và $\frac{1}{base^k}$

#define int long long
const int BASE = 311;
const int MOD = int(1e9)+7
int pwr[MAX + 1];        // power
int inv[MAX + 1];        // inverse

pwr[0] = 1;
for (int i = 1; i <= MAX; i++)
    pwr[i] = pwr[i - 1] * BASE % MOD;
inv[MAX] = power(pwr[MAX], MOD - 2)
for (int i = MAX - 1; i >= 0; i--)
    inv[i] = inv[i + 1] * BASE % MOD;
// tự cài lại hàm mũ power đê <(")

### Bước 2
Xây dựng mảng cộng dồn để tính hash của các xâu $s[1..i]\ (i \in [1..len_S])$

// lenS = s.length(); s = ' ' + s;
int hsh[MAX + 1] = {};

for (int i = 1; i <= lenS; i++)
    hsh[i] = hsh[i - 1] + (s[i] * pwr[i]);

### Truy vấn
Hãy trả về hash của xâu $s[l..r]$.
Chúng ta sẽ sử dụng tính chất của mảng cộng dồn.

int getHash(int l, int r){
    return (hsh[r] + MOD - hsh[l-1]) * inv[l-1] % MOD;
}

## Hash nhiều MOD
Để tăng độ chính xác, chúng ta cần hash cho nhiều MOD trở lên. Ví dụ: $10^9+2277, 10^9+5277, 10^9+8277, 10^9+9277$.
### Bước 0. Xác định BASE, MOD

const int BASE = 311;
const int MOD[4] = {int(1e9)+2277, int(1e9)+5277, int(1e9)+8277, int(1e9)+9277};
const int USEMOD = 2;

### Bước -1. Định nghĩa kiểu dữ liệu Hash

// về nhà học struct class.
#define int long long
struct Hash{
    int value[USEMOD] = {};
    Hash(){
        for (int i = 0; i < USEMOD; i++) 
            value[i] = 0;
    }
    Hash(int x){
        for (int i = 0; i < USEMOD; i++) 
            value[i] = x % MOD[i];
    }
};

Hash operator + (Hash a, Hash b){
    Hash answer;
    for (int i= 0; i < USEMOD; i++)
        answer.value[i] = (a.value[i] + b.value[i]) % MOD[i];
    return answer;
}
Hash operator - (Hash a, Hash b){
    Hash answer;
    for (int i= 0; i < USEMOD; i++)
        answer.value[i] = (a.value[i] + MOD[i] - b.value[i]) % MOD[i];
    return answer;
}
Hash operator * (Hash a, Hash b){
    Hash answer;
    for (int i= 0; i < USEMOD; i++)
        answer.value[i] = (a.value[i] * b.value[i]) % MOD[i];
    return answer;
}
Hash operator * (Hash a, int b){
    Hash answer;
    for (int i= 0; i < USEMOD; i++)
        answer.value[i] = (a.value[i] * b) % MOD[i];
    return answer;
}
bool operator == (Hash a, Hash b){
    bool answer = true;
    for (int i = 0; i < USEMOD; i++)
        answer &= a.value[i] == b.value[i];
    return answer;
}

### Bước 1. Khởi tạo mảng

Hash pwr[MAX + 1], inv[MAX + 1];
for (int i = 1; i <= MAX; i++)
    pwr[i] = pwr[i-1] * BASE;
// tính inv[MAX]
for (int i = 0; i < USEMOD; i++)
    inv[MAX].value[i] = power(pwr[MAX].value[i], MOD[i] - 2, MOD[i]); // power(a, n, mod)
// tính full mảng inv
for (int i = MAX - 1; i >= 0; i--)
    inv[i] = inv[i + 1] * BASE;

### Bước 2. Dựng mảng cộng dồn

// lenS = s.length(); s = ' ' + s;
Hash hsh[MAX + 1] = {};

for (int i = 1; i <= lenS; i++)
    hsh[i] = hsh[i - 1] + Hash(s[i]) * pwr[i];

### Bước 3. Truy vấn

Hash getHash(int l, int r){
    return (hsh[r] - hsh[l-1]) * inv[l-1];
}

## Giải bài tập
### CSES1753 - String Matching
Gọi xâu độ dài $n$ là $S$, xâu độ dài $m$ là $T$.

Mình sẽ thử từng xâu con có độ dài $m$ của $S$. Nếu trùng với $T$ (có hash = $T$) thì ghi nhận.

const int HASH_T = (tự tính hash của T đi <("))
int answer = 0;
for (int l = 1, r = m; r <= n; l++, r++)
    if (getHash(l, r) == HASH_T)
        answer++;

### Pun
Nếu như độ dài lớn nhất thỏa mãn đề là $d$ thì toàn bộ các giá trị $d' < d$ đều thỏa mãn đề.

Từ tính chất này, chúng ta có thể sử dụng chặt nhị phân.
Ở vị trí $mid$:
- Nếu $mid$ thỏa mãn $\Rightarrow$ toàn bộ đáp án $< mid$ cũng thỏa mãn $\Rightarrow$ không cần xét bên trái $\Rightarrow$ ghi nhận đáp án $mid$ và $l = mid + 1$
- Nếu không thỏa mãn thì toàn bộ bên phải cũng không thỏa mãn $\Rightarrow r = mid - 1$

bool check(int len){
    map<int, int> firsttime;
    for (int beg = 1, end = len; end <= n; beg++, end++){
        int value = getHash(beg, end);
        if (firsttime[value] == 0) // chưa xuất hiện
            firsttime[value] = beg;
        else if (beg - firsttime[value] >= len)
            return true;
    }
    return false;
}

lo = 1, hi = n, ans = 0;
while (lo <= hi){
    mid = (lo + hi) / 2;
    if (check(mid))
        ans = mid, lo = mid + 1;
    else
        hi = mid - 1;
}
cout << ans;

### Tìm chu kỳ

// len = s.length(); s = ' ' + s;
bool check(int len){
    // kiểm tra độ dài len có thỏa mãn không.
    int hshFirst = getHash(1, len);
    for (int beg = len + 1; beg <= n; beg += len){
        int end = beg + len - 1;
        if (end <= n){
            if (hshFirst != getHash(beg, end))
                return false;
        } else {
            end = n; len = end - beg + 1; // cuối xâu rồi, gán lại k sao hết
            if (getHash(1, len) != getHash(beg, end))
                return false;
        }
    }
    return true;
}

int answer = 0;
for (int i = 1; i <= n; i++)
    cout << i << ' ';

### VOSTR
Khi so sánh theo thứ tự từ điển, ta tìm vị trí đầu tiên mà hai ký tự tương ứng của hai xâu khác nhau.

Vì vậy, với mỗi truy vấn $(l,r,u,v)$, ta tìm $k\ (0\le k \le \min(r-l+1, v-u+1))$ nhỏ nhất sao cho $a[l+k] \ne b[u+k]$.

Ta sẽ tìm $k$ sử dụng tìm kiếm nhị phân: Với mỗi $k$, ta so sánh $a[l..l+k]$ và $b[u..u+k]$. Tất nhiên, để so sánh cho nhanh, ta dùng HASH =)). Nếu hai xâu bằng nhau thì `l = mid + 1`, ngược lại ghi nhận `mid` làm đáp án và `r = mid - 1`

### PALINX
Có ba trường hợp ghép xâu palindrome:
- `abacc|ccaba`
- `abd(cc)|dba`
- `dba|(aa)abd`

Với `(...)` là phần ở giữa của xâu palindrome.

Với mỗi xâu đề cho, ta lưu hai phiên bản Hash: một bản của xâu gốc, một bản của xâu bị đảo ngược.

// định nghĩa Hash operator < (Hash a, Hash b) để dùng map
map<Hash, int> save; // lưu các phiên bản đảo ngược

ll answer = 0;
for (int i = 1; i <= n; i++){
    // th1: abacc nối với ccaba
    answer += save[xâu đảo(s[i])];
    // th2: abd(cc) nối với dba, tức là trụ palindrome nằm bên phải xâu
    for (int j = n; j >= 2; j--)
        if (s[j..n] là palindrome)
            answer += save[xâu đảo(s[1..j-1])]
    // th3: trụ nằm bên trái xâu
    for (int j = 2; j <= n; j++)
        if (s[1..j] là palindrome)
            answer += save[xâu đảo(s[j+1..n])]
}

### EXTPALIN - Tạo palindrome
Giống trường hợp 2 của bài trên => tìm j nhỏ nhất sao cho s[j..n] là palindrome.

a
a
a
a
a
a
a
a
a
a
a
a
a
a