#include <bits/stdc++.h> using namespace std; char cs[50050]; char seq[50050]; unordered_map<string, int> counts; void f(int p, int c, int n) { if(p == n) { string s(seq, c); counts[s]++; return; } seq[c++] = cs[p]; for(int i = p + 1; i <= n; i++) { f(i, c, n); } seq[c--] = 0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; cin >> cs; for(int i = 0; i < n; i++) { f(i, 0, n); } int r = 0; for(auto i: counts) { r += i.second > 1; } cout << r << "\n"; while(q--) { int p; char z; cin >> p >> z; cs[--p] = z; counts.clear(); for(int i = 0; i < n; i++) { f(i, 0, n); } int r = 0; for(auto i: counts) { r += i.second > 1; } cout << r << "\n"; } return 0; }
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include <bits/stdc++.h> using namespace std; char cs[50050]; char seq[50050]; unordered_map<string, int> counts; void f(int p, int c, int n) { if(p == n) { string s(seq, c); counts[s]++; return; } seq[c++] = cs[p]; for(int i = p + 1; i <= n; i++) { f(i, c, n); } seq[c--] = 0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; cin >> cs; for(int i = 0; i < n; i++) { f(i, 0, n); } int r = 0; for(auto i: counts) { r += i.second > 1; } cout << r << "\n"; while(q--) { int p; char z; cin >> p >> z; cs[--p] = z; counts.clear(); for(int i = 0; i < n; i++) { f(i, 0, n); } int r = 0; for(auto i: counts) { r += i.second > 1; } cout << r << "\n"; } return 0; } |