Advertisement
willy108

CSES 1110

Oct 1st, 2021
1,488
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.73 KB | None | 0 0
  1. std::vector<int> sa_naive(const std::vector<int>& s) {
  2.     int n = int(s.size());
  3.     std::vector<int> sa(n);
  4.     std::iota(sa.begin(), sa.end(), 0);
  5.     std::sort(sa.begin(), sa.end(), [&](int l, int r) {
  6.         if (l == r) return false;
  7.         while (l < n && r < n) {
  8.             if (s[l] != s[r]) return s[l] < s[r];
  9.             l++;
  10.             r++;
  11.         }
  12.         return l == n;
  13.     });
  14.     return sa;
  15. }
  16.  
  17. std::vector<int> sa_doubling(const std::vector<int>& s) {
  18.     int n = int(s.size());
  19.     std::vector<int> sa(n), rnk = s, tmp(n);
  20.     std::iota(sa.begin(), sa.end(), 0);
  21.     for (int k = 1; k < n; k *= 2) {
  22.         auto cmp = [&](int x, int y) {
  23.             if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
  24.             int rx = x + k < n ? rnk[x + k] : -1;
  25.             int ry = y + k < n ? rnk[y + k] : -1;
  26.             return rx < ry;
  27.         };
  28.         std::sort(sa.begin(), sa.end(), cmp);
  29.         tmp[sa[0]] = 0;
  30.         for (int i = 1; i < n; i++) {
  31.             tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
  32.         }
  33.         std::swap(tmp, rnk);
  34.     }
  35.     return sa;
  36. }
  37.  
  38. // SA-IS, linear-time suffix array construction
  39. // Reference:
  40. // G. Nong, S. Zhang, and W. H. Chan,
  41. // Two Efficient Algorithms for Linear Time Suffix Array Construction
  42. template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
  43. std::vector<int> sa_is(const std::vector<int>& s, int upper) {
  44.     int n = int(s.size());
  45.     if (n == 0) return {};
  46.     if (n == 1) return {0};
  47.     if (n == 2) {
  48.         if (s[0] < s[1]) {
  49.             return {0, 1};
  50.         } else {
  51.             return {1, 0};
  52.         }
  53.     }
  54.     if (n < THRESHOLD_NAIVE) {
  55.         return sa_naive(s);
  56.     }
  57.     if (n < THRESHOLD_DOUBLING) {
  58.         return sa_doubling(s);
  59.     }
  60.  
  61.     std::vector<int> sa(n);
  62.     std::vector<bool> ls(n);
  63.     for (int i = n - 2; i >= 0; i--) {
  64.         ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  65.     }
  66.     std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
  67.     for (int i = 0; i < n; i++) {
  68.         if (!ls[i]) {
  69.             sum_s[s[i]]++;
  70.         } else {
  71.             sum_l[s[i] + 1]++;
  72.         }
  73.     }
  74.     for (int i = 0; i <= upper; i++) {
  75.         sum_s[i] += sum_l[i];
  76.         if (i < upper) sum_l[i + 1] += sum_s[i];
  77.     }
  78.  
  79.     auto induce = [&](const std::vector<int>& lms) {
  80.         std::fill(sa.begin(), sa.end(), -1);
  81.         std::vector<int> buf(upper + 1);
  82.         std::copy(sum_s.begin(), sum_s.end(), buf.begin());
  83.         for (auto d : lms) {
  84.             if (d == n) continue;
  85.             sa[buf[s[d]]++] = d;
  86.         }
  87.         std::copy(sum_l.begin(), sum_l.end(), buf.begin());
  88.         sa[buf[s[n - 1]]++] = n - 1;
  89.         for (int i = 0; i < n; i++) {
  90.             int v = sa[i];
  91.             if (v >= 1 && !ls[v - 1]) {
  92.                 sa[buf[s[v - 1]]++] = v - 1;
  93.             }
  94.         }
  95.         std::copy(sum_l.begin(), sum_l.end(), buf.begin());
  96.         for (int i = n - 1; i >= 0; i--) {
  97.             int v = sa[i];
  98.             if (v >= 1 && ls[v - 1]) {
  99.                 sa[--buf[s[v - 1] + 1]] = v - 1;
  100.             }
  101.         }
  102.     };
  103.  
  104.     std::vector<int> lms_map(n + 1, -1);
  105.     int m = 0;
  106.     for (int i = 1; i < n; i++) {
  107.         if (!ls[i - 1] && ls[i]) {
  108.             lms_map[i] = m++;
  109.         }
  110.     }
  111.     std::vector<int> lms;
  112.     lms.reserve(m);
  113.     for (int i = 1; i < n; i++) {
  114.         if (!ls[i - 1] && ls[i]) {
  115.             lms.push_back(i);
  116.         }
  117.     }
  118.  
  119.     induce(lms);
  120.  
  121.     if (m) {
  122.         std::vector<int> sorted_lms;
  123.         sorted_lms.reserve(m);
  124.         for (int v : sa) {
  125.             if (lms_map[v] != -1) sorted_lms.push_back(v);
  126.         }
  127.         std::vector<int> rec_s(m);
  128.         int rec_upper = 0;
  129.         rec_s[lms_map[sorted_lms[0]]] = 0;
  130.         for (int i = 1; i < m; i++) {
  131.             int l = sorted_lms[i - 1], r = sorted_lms[i];
  132.             int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
  133.             int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
  134.             bool same = true;
  135.             if (end_l - l != end_r - r) {
  136.                 same = false;
  137.             } else {
  138.                 while (l < end_l) {
  139.                     if (s[l] != s[r]) {
  140.                         break;
  141.                     }
  142.                     l++;
  143.                     r++;
  144.                 }
  145.                 if (l == n || s[l] != s[r]) same = false;
  146.             }
  147.             if (!same) rec_upper++;
  148.             rec_s[lms_map[sorted_lms[i]]] = rec_upper;
  149.         }
  150.  
  151.         auto rec_sa =
  152.             sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
  153.  
  154.         for (int i = 0; i < m; i++) {
  155.             sorted_lms[i] = lms[rec_sa[i]];
  156.         }
  157.         induce(sorted_lms);
  158.     }
  159.     return sa;
  160. }
  161.  
  162. }  // namespace internal
  163.  
  164. std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
  165.     assert(0 <= upper);
  166.     for (int d : s) {
  167.         assert(0 <= d && d <= upper);
  168.     }
  169.     auto sa = internal::sa_is(s, upper);
  170.     return sa;
  171. }
  172.  
  173. template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
  174.     int n = int(s.size());
  175.     std::vector<int> idx(n);
  176.     iota(idx.begin(), idx.end(), 0);
  177.     sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
  178.     std::vector<int> s2(n);
  179.     int now = 0;
  180.     for (int i = 0; i < n; i++) {
  181.         if (i && s[idx[i - 1]] != s[idx[i]]) now++;
  182.         s2[idx[i]] = now;
  183.     }
  184.     return internal::sa_is(s2, now);
  185. }
  186.  
  187. std::vector<int> suffix_array(const std::string& s) {
  188.     int n = int(s.size());
  189.     std::vector<int> s2(n);
  190.     for (int i = 0; i < n; i++) {
  191.         s2[i] = s[i];
  192.     }
  193.     return internal::sa_is(s2, 255);
  194. }
  195.  
  196. // Reference:
  197. // T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
  198. // Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
  199. // Applications
  200. template <class T>
  201. std::vector<int> lcp_array(const std::vector<T>& s,
  202.                            const std::vector<int>& sa) {
  203.     int n = int(s.size());
  204.     assert(n >= 1);
  205.     std::vector<int> rnk(n);
  206.     for (int i = 0; i < n; i++) {
  207.         rnk[sa[i]] = i;
  208.     }
  209.     std::vector<int> lcp(n - 1);
  210.     int h = 0;
  211.     for (int i = 0; i < n; i++) {
  212.         if (h > 0) h--;
  213.         if (rnk[i] == 0) continue;
  214.         int j = sa[rnk[i] - 1];
  215.         for (; j + h < n && i + h < n; h++) {
  216.             if (s[j + h] != s[i + h]) break;
  217.         }
  218.         lcp[rnk[i] - 1] = h;
  219.     }
  220.     return lcp;
  221. }
  222.  
  223. std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
  224.     int n = int(s.size());
  225.     std::vector<int> s2(n);
  226.     for (int i = 0; i < n; i++) {
  227.         s2[i] = s[i];
  228.     }
  229.     return lcp_array(s2, sa);
  230. }
  231.  
  232. // Reference:
  233. // D. Gusfield,
  234. // Algorithms on Strings, Trees, and Sequences: Computer Science and
  235. // Computational Biology
  236. template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
  237.     int n = int(s.size());
  238.     if (n == 0) return {};
  239.     std::vector<int> z(n);
  240.     z[0] = 0;
  241.     for (int i = 1, j = 0; i < n; i++) {
  242.         int& k = z[i];
  243.         k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
  244.         while (i + k < n && s[k] == s[i + k]) k++;
  245.         if (j + z[j] < i + z[i]) j = i;
  246.     }
  247.     z[0] = n;
  248.     return z;
  249. }
  250.  
  251. std::vector<int> z_algorithm(const std::string& s) {
  252.     int n = int(s.size());
  253.     std::vector<int> s2(n);
  254.     for (int i = 0; i < n; i++) {
  255.         s2[i] = s[i];
  256.     }
  257.     return z_algorithm(s2);
  258. }
  259. int main(){
  260.   cin.tie(0) -> sync_with_stdio(0);
  261.     string s;
  262.     cin >> s;
  263.     s += s;
  264.     vector<int> saa= suffix_array(s);
  265.     int k = 0;
  266.     for(; saa[k] >= sz(s)/2; k++){}
  267.  
  268.     for(int i = saa[k]; i < sz(s)/2; i++){
  269.         cout << s[i];
  270.     }
  271.     for(int i = 0; i<saa[k]; i++){
  272.         cout << s[i];
  273.     }
  274.   return 0;
  275. }
  276.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement