# **Hash (Rabin–Karp)**
## 1. Bài toán:
Cho xâu $A$ và xâu $B$ chỉ gồm các chữ cái thường. Xâu $B$ được gọi là xuất hiện trong vị trí $i$ của xâu $A$ nếu $A$~i~ $=$ $B$~1~, $A$~i+1~ $=$ $B$~2~,..., $A$~i+length(B)-1~ $=$ $B$~length(B)~. Hãy tìm tất cả vị trí mà $B$ xuất hiện trong $A$.

***Input:***
* Dòng 1: xâu $A$.
* Dòng 2: xâu $B$.

***Output:***
* Ghi ra các vị trí tìm được trên dòng (thứ tự tăng dần). Nếu $B$ không xuất hiện trong $A$ thì bỏ trắng.

***Sample input:***

aaaaa
aa

***Sample output:***

1 2 3 4

## 2. Thuật toán ngây thơ

#include <bits/stdc++.h> 
using namespace std;
#define ll long long

int main() {
    string a, b; cin >> a >> b;
    int n = a.size(), m = b.size();
    for(int i = 0; i < n - m + 1; i++) {
        string x = a.substr(i, m);
        if(b == x) cout << i + 1 << " ";
    }
    return 0;
}

**Độ phức tạp thời gian: $O(n * m)$**.

## 3. Thuật toán Hash
Ta sẽ biểu diễn một xâu dưới dạng một số của hệ cơ số thay vì chữ cái thông thường. Ví dụ $string$ $a$ $=$ "$abbz$", viết ở dạng số sẽ là $[1, 2, 2, 26]$, ta sẽ biểu diễn dưới dạng một hệ cơ số $base$ với $base$ $>$ $26$.Vậy, hai xâu bằng nhau khi biểu diễn của hai xâu ở hệ cơ số 10 giống nhau.

Tư tưởng của thuật toán là đổi từ hệ cơ số $base$ sang hệ cơ số 10 rồi so sánh ở hệ cơ số 10 nên cũng có khả năng nằm ngoài phạm vi lưu trữ của máy tính. Để khắc phục điều này ta sẽ lấy dư cho $MOD$ với $MOD$ $=$ $10^9 + 7$.

$-$ Cơ số 10 là các số $∈$ $[0 ; 9]$:
* Ví dụ: $12345$ = $1×10^4 + 2×10^3 + 3×10^2 + 4×10^1 + 5×10^0$

$-$ Cơ số 2 là các số $∈$ $[0 ; 1]$:
* Ví dụ: $11011$

$-$ Các hệ cơ số còn lại cũng tương tự.

### 3.1. Tính hash của b
Giả sử ta có xâu $b$ = "$abc$" (chọn $base$ = 300). Vậy ở dạng số thì xâu $b$ sẽ là "$97$ $98$ $99$",
Hash của $b$ $=$ $(97×300^2 + 98×300^1 + 99×300^0)$ $=$ hash($b$~1~...$b$~m~)
$=$ ($b$~1~ $×$ $base$^m-1^ $+$ $b$~2~$× base$^m-2^ $+$ ... $+$ $b$~m-1~$~×base^1$ $+$ $b$~m~).
### 3.2. Tính pow và sum

ll POW[1000009], sum[1000009];
POW[0] = 1;
for(int i = 1; i <= m; i++) {
    POW[i] = (POW[i - 1] * base) % MOD;
}
sum[0] = 0;
for(int i = 1; i <= n; i++) {
    sum[i] = (sum[i - 1] * base + a[i]) % MOD;
}

### 3.3. Implement

// author : hatakaze (a.k.a Tran Gia Huy)
#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define ll long long

const ll MOD = 1e9 + 7;

string a, b;
const long long maxn = 1e6 + 9;
const ll base = 300;
ll POW[1000009], sum[1000009];

ll getHash(int i, int j) {
    return ((sum[j] - sum[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD);
}
void solve() {
    cin >> a >> b;
    int n = sz(a), m = sz(b);
    a = " " + a;
    b = " " + b;
    ll HashB = 0;
    for(int i = 1; i <= m; i++) {
        HashB = (HashB * base + b[i]) % MOD;
    }
    POW[0] = 1;
    for(int i = 1; i <= m; i++) {
        POW[i] = (POW[i - 1] * base) % MOD;
    }
    sum[0] = 0;
    for(int i = 1; i <= n; i++) {
        sum[i] = (sum[i - 1] * base + a[i]) % MOD;
    }
    for(int i = 1; i <= n - m + 1; i++) {
        if(getHash(i, i + m - 1) == HashB) {
            cout << i << " ";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

**Tài liệu tham khảo:**
* https://vnoi.info/wiki/algo/string/hash.md