#include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; const ll mod = 1e9+123; const ll p = 29; ll calc(string& s){ unordered_map<ll, ll> mp; mp[0] = 1; for(auto c: s){ vector<pair<ll, ll>> to_add; for(auto [hsh, cnt]: mp){ to_add.push_back({(hsh*p+c-'a'+1)%mod, cnt}); } for(auto [hsh, cnt]: to_add){ mp[hsh] += cnt; } } ll res = 0; for(auto [hsh, cnt]: mp){ res += cnt > 1; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin>>n>>q; string s; cin>>s; cout<<calc(s)<<nl; while(q--){ int pos; char c; cin>>pos>>c; s[pos-1] = c; cout<<calc(s)<<nl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; const ll mod = 1e9+123; const ll p = 29; ll calc(string& s){ unordered_map<ll, ll> mp; mp[0] = 1; for(auto c: s){ vector<pair<ll, ll>> to_add; for(auto [hsh, cnt]: mp){ to_add.push_back({(hsh*p+c-'a'+1)%mod, cnt}); } for(auto [hsh, cnt]: to_add){ mp[hsh] += cnt; } } ll res = 0; for(auto [hsh, cnt]: mp){ res += cnt > 1; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin>>n>>q; string s; cin>>s; cout<<calc(s)<<nl; while(q--){ int pos; char c; cin>>pos>>c; s[pos-1] = c; cout<<calc(s)<<nl; } } |