Solutions of Gnimmah distance - MarisaOJ: Marisa Online Judge

Solutions of Gnimmah distance

Select solution language

Write solution here.


User Avatar Long4200    Created at    3 likes

### 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; } ```