# **Lưu ý: Hãy tự nghĩ cách giải, chỉ xem sol khi bí**
# **Ý TƯỞNG**:
Đề bài yêu cầu ta xác định số lần xuất hiện của `string` $S$ trong `string` $T$
### **SỬ DỤNG HASH :**
Các bạn có thể tham khảo ý tưởng thuật toán chi tiết ở đây: [Hash: A String Matching Algorithm](https://wiki.vnoi.info/algo/string/hash.md).
Tóm gọn: thay vì ta so sánh `string` với `string`. Ta sẽ so sánh hệ cơ số 10 của `string` $T$ và `string` $S$. Tuy nhiên, ta nhận thấy rằng, khi đổi 1 `string` ra biểu diễn ở hệ cơ số 10, biểu diễn này có thể **rất lớn** và nằm ngoài phạm vi lưu trữ số nguyên của máy tính.
$\Rightarrow$ Ta cần chia dư cho `MOD = 1e9 + 7`.
### **CHÚ Ý :**
Ta có thể từ:
$a = b \\Rightarrow\ a \bmod M = b \bmod M$
Nhưng mà **KHÔNG THỂ** từ:
$a \bmod M = b \bmod M \\Rightarrow\ a = b$
**CODE THAM KHẢO :**
```cpp
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define FOR(i, l, r) for (ll i = l; i <= r; i++)
#define fre(NAME) freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout)
#define ALL(a) a.begin(), a.end()
#define suyvolo ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ldb long double
const ll INF = 4e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 5;
const ll MAXT = 1e3+10;
const int base = 31;
using namespace std;
// THPT Tran Phu TpHCM
ll POW[MAXN], hashT[MAXN];
ll getHashT(ll i,ll j){ // Hàm tính Hash T
return(hashT[j] - hashT[i-1] * POW[j-i+1] + MOD * MOD)%MOD;
}
int main(){
suyvolo;
string t,s;
cin >> t >> s;
ll len_t= t.size(), len_s = s.size();
t = " " + t; // cộng " " vào để biến chuỗi ở dạng 0-based -> 1 based
s = " " + s;
POW[0] = 1;
FOR(i,1,len_t){ // 1-based
POW[i] = (POW[i-1] *base) % MOD;
}
FOR(i,1,len_t){
hashT[i] = (hashT[i-1] * base + t[i] - 'a' +1) %MOD;
}
// Tính Hash S
ll hashS = 0;
FOR(i,1,len_s) {
hashS = (hashS*base + s[i] - 'a' +1) %MOD;
}
ll cnt =0;
FOR(i,1,len_t - len_s +1){
if(hashS == getHashT(i, i + len_s -1)){
cnt++;
}
}
cout << cnt;
return 0;
}
/*
Have a nice day. =D
*/
```
angwangsushi
Created at
0 likes