fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. struct SuffixArray {
  8.  
  9.     int n;
  10.     string s;
  11.     vector<int> suf, classes, lcp;
  12.  
  13.     SuffixArray(string& str) {
  14.         s = str + char(0), n = s.size();
  15.         build();
  16.         calc_lcp();
  17.     }
  18.  
  19.     void count_sort(vector<int> &suf, vector<int> &classes) {
  20.         int n = suf.size(), d = 2;
  21.         vector<int> freq(n), pos(n);
  22.         for (int i = 0; i < n; i++) {
  23.             freq[classes[i]]++;
  24.         }
  25.  
  26.         pos = freq;
  27.         for (int i = 1; i < n; i++) {
  28.             pos[i] += pos[i - 1];
  29.         }
  30.  
  31.         vector<int> new_suf(n);
  32.         for (int i = n - 1; i >= 0; i--) {
  33.             int x = classes[suf[i]];
  34.             pos[x]--;
  35.             new_suf[pos[x]] = suf[i];
  36.         }
  37.         suf = new_suf;
  38.     }
  39.     void build() {
  40.         suf.resize(n);
  41.         classes.resize(n);
  42.  
  43.         // k = 0
  44.         vector<pair<char, int> > a(n);
  45.         for (int i = 0; i < n; i++) {
  46.             a[i] = {s[i], i};
  47.         }
  48.         sort(a.begin(), a.end());
  49.  
  50.         for (int i = 0; i < n; i++) {
  51.             suf[i] = a[i].second;
  52.         }
  53.         for (int i = 1; i < n; i++) {
  54.             classes[suf[i]] = classes[suf[i - 1]] + (a[i].first != a[i - 1].first);
  55.         }
  56.  
  57.         int k = 0;
  58.         while ((1 << k) < n) {
  59.             // k -> k + 1
  60.             for (int i = 0; i < n; i++) {
  61.                 suf[i] = (suf[i] - (1 << k) + n) % n;
  62.             }
  63.             count_sort(suf, classes);
  64.  
  65.             vector<int> c(n);
  66.             c[suf[0]] = 0;
  67.             for (int i = 1; i < n; i++) {
  68.                 pair<int, int> cur = {classes[suf[i]], classes[(suf[i] + (1 << k)) % n]};
  69.                 pair<int, int> prv = {classes[suf[i - 1]], classes[(suf[i - 1] + (1 << k)) % n]};
  70.                 c[suf[i]] = c[suf[i - 1]] + (cur != prv);
  71.             }
  72.             classes = c;
  73.             k++;
  74.         }
  75.     }
  76.     int comp(int i, const string& t) {
  77.         int j = 0;
  78.         while (i < n && j < t.size() && s[i] == t[j]) {
  79.             i++, j++;
  80.         }
  81.  
  82.         if (i == n && j == t.size())
  83.             return 0;
  84.         if (i == n)
  85.             return -1;
  86.         if (j == t.size())
  87.             return 1;
  88.         if (s[i] < t[j])return -1;
  89.         return 1;
  90.     }
  91.     bool is_prefix(int ind, const string& t) {
  92.         bool ok = true;
  93.         int i = suf[ind], j = 0;
  94.         while (i < n && j < t.size() && ok) {
  95.             ok &= s[i] == t[j];
  96.             i++, j++;
  97.         }
  98.         return ok;
  99.     }
  100.     int find_string(const string& t) {
  101.         int l = 0, r = n - 1, ans = -1;
  102.         while (l <= r) {
  103.             int mid = (l + r) / 2;
  104.             if (comp(suf[mid], t) >= 0) {
  105.                 ans = mid;
  106.                 r = mid - 1;
  107.             }
  108.             else {
  109.                 l = mid + 1;
  110.             }
  111.         }
  112.         if (ans == -1)
  113.             return -1;
  114.         return is_prefix(ans, t) ? ans : -1;
  115.     }
  116.     int count_string(const string& t) {
  117.         int index = find_string(t);
  118.         if (index == -1)
  119.             return 0;
  120.  
  121.         int l = index, r = n - 1, ans = -1;
  122.         while (l <= r) {
  123.             int mid = (l + r) / 2;
  124.             if (is_prefix(mid, t)) {
  125.                 ans = mid;
  126.                 l = mid + 1;
  127.             }
  128.             else {
  129.                 r = mid - 1;
  130.             }
  131.         }
  132.         return ans - index + 1;
  133.     }
  134.     void calc_lcp() {
  135.         lcp.resize(n);
  136.         int k = 0;
  137.         for (int i = 0; i < n - 1; i++) {
  138.             int pi = classes[i];
  139.             int j = suf[pi - 1];
  140.             while (s[i + k] == s[j + k])k++;
  141.             lcp[pi] = k;
  142.             k = max(k - 1, 0ll);
  143.         }
  144.     }
  145. };
  146. long long calc_distinct_substring(string& s) {
  147.     SuffixArray sa(s);
  148.     long long ans = 0;
  149.     for (int i = 1; i < sa.lcp.size(); i++) {
  150.         int sz = sa.n - sa.suf[i] - 1;
  151.         ans += (sz - sa.lcp[i]);
  152.     }
  153.     return ans;
  154. }
  155. pair<int, int> lcs(string& s, string& t) {
  156.     int n = s.size(), m = t.size();
  157.     string y = s + '$' + t;
  158.     SuffixArray sa(y); // 0..n-1 -> s, n+1..n+m -> t
  159.  
  160.     // for (int i = 0; i < sa.n; i++) {
  161.     //     cout << sa.suf[i] << " " << sa.lcp[i] << " " << sa.s.substr(sa.suf[i]) << "\n";
  162.     // }
  163.  
  164.     int maximum = 0, index = 0;
  165.     for (int i = 0; i + 1 <= n + m + 1; i++) {
  166.         if (sa.suf[i] <= n - 1 && n + 1 <= sa.suf[i + 1]) {
  167.             if (maximum < sa.lcp[i + 1]) {
  168.                 index = sa.suf[i];
  169.                 maximum = sa.lcp[i + 1];
  170.             }
  171.         }
  172.         else if (sa.suf[i + 1] <= n - 1 && n + 1 <= sa.suf[i]) {
  173.             if (maximum < sa.lcp[i + 1]) {
  174.                 index = sa.suf[i + 1];
  175.                 maximum = sa.lcp[i + 1];
  176.             }
  177.         }
  178.     }
  179.     return {index, maximum};
  180. }
  181.  
  182. int32_t main() {
  183.     ios::sync_with_stdio(false);
  184.     cin.tie(nullptr), cout.tie(nullptr);
  185.  
  186.     int tests;
  187.     cin >> tests;
  188.  
  189.     for (int _ = 1; _ <= tests; _++) {
  190.         int n;
  191.         cin >> n;
  192.  
  193.         string s;
  194.         cin >> s;
  195.  
  196.         int l = 0, r = n - 1, distinct = 0;
  197.         vector<int> freq(26);
  198.         for (auto& i : s) {
  199.             freq[i - 'a']++;
  200.             if (freq[i - 'a'] == 1)
  201.                 distinct++;
  202.         }
  203.  
  204.         while (l < r) {
  205.             char c = 'a' + distinct - 1;
  206.             if (c <= s[l]) {
  207.                 freq[s[l] - 'a']--;
  208.                 if (freq[s[l] - 'a'] == 0)
  209.                     distinct--;
  210.                 l++;
  211.                 continue;
  212.             }
  213.             // if (c == s[l]) {
  214.             //     assert(0);
  215.             // }
  216.             break;
  217.         }
  218.  
  219.         while (l < r) {
  220.             int dx = freq[s[r] - 'a'] == 1;
  221.             if (dx) {
  222.                 break;
  223.             }
  224.             freq[s[r] - 'a']--;
  225.             if (freq[s[r] - 'a'] == 0)
  226.                 distinct--;
  227.             r--;
  228.         }
  229.  
  230.  
  231.         for (int i = 0; i < l; i++) cout << s[i];
  232.         cout << char('a' + distinct - 1);
  233.  
  234.         if (r != n - 1) {
  235.             string t = s.substr(r + 1);
  236.             SuffixArray sa(t);
  237.             t = t.substr(sa.suf.back());
  238.             cout << t;
  239.         }
  240.         // for (int i = r + 1; i < n; i++) cout << s[i];
  241.         cout << "\n";
  242.     }
  243.  
  244.     return 0;
  245. }
Success #stdin #stdout 0.01s 5252KB
comments (?)
stdin
copy 
1
5
edcab
stdout
copy 
edcb
https://ideone.com/QAGWzQ
1
5
edcab
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!