[toc]
## Dạng bài
- Cho một xâu $T$ (text) và xâu $P$ (pattern). Tìm tất cả các lần xuất hiện của xâu $P$ trong xâu $T$.
## Thuật toán vét cạn
Là thuật toán so khớp chuỗi "ngây thơ"
### Ý tưởng
Trượt và so sánh các ký tự trong chuỗi $P$ đã cho với chuỗi $T$ từng ký tự một.
### Độ phức tạp
- $O(|P|*|T|)$ cho tất cả trường hợp
### Cài đặt

for (int i=0; i<=T.size()-P.size(); i++){ // i là vị trí bắt đầu so khớp
    bool match = 1;
    for (int j=0; j<P.size(); j++){
        if (P[j] != T[i+j]){
            match = 0;
            break;
        }
    }
    if (match == 1){
        cout<<i<<" ";
    }
}

## Thuật toán Knuth-Morris-Pratt (KMP)
### Hàm tiền tố
- Định nghĩa: Hàm tiền tố cho một chuỗi $s$ độ dài $n$ là một mảng $pi$ độ dài $n$, mà $p[i]$ là độ dài dài nhất (không bằng chính nó) của chuỗi con vừa là tiền tố vừa là hậu tố trong chuỗi con $s[0…i]$.
+ $pi[0] = 0$
+ $pi[i]=max(k)$ với $k=0,1,…,i$ sao cho $s[0…(k-1)]=s[(i-k+1)...i]$
- Ví dụ:

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| s[i] | a | a | b | c | a | a | b | c | d | a |
| pi[i] | 0 | 1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

- Ý tưởng tối ưu:
+ Nhận xét 1: Các giá trị của hàm tiền tố chỉ có thể tăng nhiều nhất một so với giá trị của vị trí trước
$0<= pi[i+1] <= pi[i]+1$


+ Nhận xét 2:
+ TH1: $s[i+1]=s[pi[i]]$, ta kết luận ngay $pi[i+1]=pi[i]+1$
+ TH2: Ngược lại, ta cần thử một chuỗi ngắn hơn, giả sử độ dài thử là $j$, ta có $s[0…(j-1)]=s[(i-j+1)...i]$, ta chỉ cần so sánh $s[i+1]$ và $s[j]$. Nếu $s[i+1]=s[j]$, ta có thể gán $pi[i+1]=j+1$. Nếu không, chúng ta sẽ cần tìm giá trị lớn nhất nhỏ hơn j mà thuộc tính tiền tố nắm giữ, cụ thể là $pi[j-1]$. Quá trình diễn ra cho đến khi $j=0$.

- Độ phức tạp: $O(|S|)$
- Cài đặt:

void prefix_Function(string s, int len, int pi[]){// ham tien to cua xau s do dai len tra ve trong mang pi
    pi[0]=0;
    for (int i=1; i<len; i++){
        int j=pi[i-1];
        while(j>0 && s[i]!=s[j]){
            j=pi[j-1];
        }
        if (s[i]==s[j]){
            pi[i]=j+1;
        }
        else{
            pi[i]=0;
        }
    }
}

### KMP dùng hàm tiền tố
- Cách xử lý:
+ Nối xâu $T$ vào sau xâu $P$ và phân tách bằng kí tự đặc biệt như '#','$'.
+ Sử dụng hàm tiền tố cho xâu sau khi nối.
+ Dựa vào định nghĩa xác định vị trí cần tìm.
- Ví dụ:
+ Cho P = aabc
+ Cho T = aabcda

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| s[i] | a | a | b | c | # | a | a | b | c | d | a |
| pi[i] | 0 | 1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

- Cài đặt:

lenP = P.size();
lenT = T.size();
P+='#'+T;
// tim ham tien to voi P
prefix_Function(P,P.size(),pi);
for (int i=lenP+1; i<lenP+lenT+1; i++){
    if (pi[i]>=lenP){
        cout<<i-2*lenP+1<<" ";
    }
}

- Độ phức tạp: $O(|P|+|T|)$

## Thuật toán Rabin Karp (Hash)
### Ý tưởng
- Đổi 2 xâu ra số ở một hệ cơ số base nào đó, rồi đem so sánh với nhau ở hệ cơ số base sau khi lấy phần dư cho một số nguyên (MOD) đủ lớn.
- Ví dụ: Chuối kí tự số '5391' biểu diễn dưới dạng hệ cơ số 10 (base=10) :
+ $((5*10 + 3)*10 + 9)*10 + 1 = 5*10^3 + 3*10^2 + 9*10^1 + 1*10^0$
- Ví dụ: Biểu diễn xâu kí tự chỉ gồm các chữ cái tiếng anh 'acbe' viết thường dưới dạng số, với $a=1, b=2,...,z=26$ (base=26)
+ $((1*26 + 3)*26 + 2)*26 + 5 = 1*26^3 + 3*26^2 + 2*26^1 + 5*26^0$
- Không những chỉ cần xác định mã hash của một xâu kí tự, ta còn cần phải xác định mã hash của xâu con của xâu kí tự đó. Gỉa sử cho xâu s[0..n-1] độ dài n, ta muốn xác định mã hash của xâu s[i...j] bất kỳ.
+ Công thức: $hash(i,j) = hash(0,j) - hash(0,i-1)*base^{j-i+1}$
+ Ví dụ: Lấy mã hash của xâu con '39' trong '5391' với base=10
+ $539 - 5*10^2 = 39$
- Lưu ý:
+ Đánh dấu xâu bắt đầu từ vị trí 1 để cài đặt dễ dàng hơn.
+ Số MOD phải là số nguyên tố đủ lớn.
### Độ phức tạp
- Độ phức tạp: $O(|P|+|T|)$
### Cài đặt

const int MAX = 1e5+5; // đồ dài lớn nhất của xâu
const int base = 256;
const int MOD = 1e9+7;

// hash xâu P
int hashP = 0;
for (int i=1; i<=P.size(); i++)
    hashP = (hashP*base + P[i]) % MOD;

// hash xâu T
int hashT[MAX], pow[MAX];
pow[0] = 1
for (int i=1; i<=T.size(); i++)
      pow[i] = (pow[i-1] * base) % MOD
hashT[0] = 0;
for (int i=1; i<=T.size(); i++)
    hashT[i] = (hashT[i-1]*base + T[i]) % MOD;

- Hàm để lấy mã hash của đoạn T[i..j] bất kỳ

int getHashT(int i, int j){
    // lưu ý do phép trừ với số mod có thể âm,
    // với 1 số ngôn ngữ như C++, toán tử mod sẽ trả kết quả sai với số âm.
    // Do đó ta cần thêm MOD*MOD để đảm bảo kết quả luôn chính xác.
    return (1ll * hashT[j] - 1ll * hashT[i-1]*pow[j-i+1] + 1ll * MOD*MOD) % MOD;
}

- Thực hiện so sánh mã hash của 2 xâu

for (int i=1; i<=T.size()-P.size()+1; i++){
    if (hashP == getHashT(i, i+P.size()-1))
        cout<<i<<" "; // in ra vị trí trùng với khuôn mẫu
}