### nhận xét: có phải là B là xâu con của A, nên B sẽ tương ứng với mọi xâu con độ dài |B| trên xâu con A
- gọi n, m lần lượt là số lượng kí tự xâu A và B
- từ đó ta lưu mỗi vị trí xuất hiện kí tự A[i] vào mảng đánh dấu vị trí gọi là pos[a[i]]
- với mỗi b[i] nó chỉ có thể xuất hiện từ vị trí tương ứng trên xâu A là từ i đến n - m + i ta cần đếm
- số lượng kí tự b[i] xuất hiện trong vị trí này và cộng vào kết quả
code mẫu:
``` cpp
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector <vector<ll>> fre(123, vector<ll> (0));
int main(){
string a, b; cin >> a >> b;
ll n = a.size(), m = b.size();
for(int i = 0; i < n; i++) {
ll c = a[i];
fre[c].pb(i);
}
ll ans = 0;
for(int i = 0; i < m; i++) {
ll r = n - m + i;
ll l = i;
ll c = b[i];
auto p1 = lower_bound(fre[c].begin(), fre[c].end(), l);
auto p2 = lower_bound(fre[c].begin(), fre[c].end(), r);
if(p1 == fre[c].end()) continue;
if(p2 == fre[c].end()) --p2;
if(*p2 > r) {
--p2;
if(p2 < p1) continue;
}
ll size = p2 - p1 + 1;
ans += size;
}
cout << ans;
}
```
Long4200
Created at
3 likes