123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149 |
- /*
- * @Description:
- * @Version: 1.0
- * @Autor: zhuyijun
- * @Date: 2021-12-23 14:37:52
- * @LastEditTime: 2021-12-28 17:13:01
- */
- /*
- 1044. 最长重复子串
- 给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2
- 次或更多次。这些出现之间可能存在重叠。
- 返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 "" 。
- 示例 1:
- 输入:s = "banana"
- 输出:"ana"
- 示例 2:
- 输入:s = "abcd"
- 输出:""
- */
- #include <bits/stdc++.h>
- using namespace std;
- class SuffixArray {
- public:
- using size_type = unsigned;
- using pointer = size_type*;
- using const_pointer = const size_type*;
- const_pointer sa, rk, ht;
- private:
- std::unique_ptr<size_type[]> data;
- private:
- template <typename S>
- inline static bool substring_equal(const S& s, size_type p1, size_type p2,
- size_type len) {
- for (size_type i = 0; i < len; ++i)
- if (s[p1 + i] != s[p2 + i]) return false;
- return true;
- }
- template <typename S>
- inline static void induced_sort(const S& s, pointer sa, bool* type,
- pointer pos, pointer lbuk, pointer sbuk,
- size_type n, size_type m, size_type n0) {
- std::fill_n(sa, n, 0);
- lbuk[0] = 0;
- for (size_type i = 1; i < m; ++i) lbuk[i] = sbuk[i - 1];
- for (size_type i = n0; i-- > 0;) sa[--sbuk[s[pos[i]]]] = pos[i];
- sbuk[m - 1] = n;
- for (size_type i = 1; i < m; ++i) sbuk[i - 1] = lbuk[i];
- sa[lbuk[s[n - 1]]++] = n - 1;
- for (size_type i = 0; i < n; ++i)
- if (sa[i] > 0 && !type[sa[i] - 1]) sa[lbuk[s[sa[i] - 1]]++] = sa[i] - 1;
- lbuk[0] = 0;
- for (size_type i = 1; i < m; ++i) lbuk[i] = sbuk[i - 1];
- for (size_type i = n; i-- > 0;)
- if (sa[i] > 0 && type[sa[i] - 1]) sa[--sbuk[s[sa[i] - 1]]] = sa[i] - 1;
- }
- template <typename S>
- inline static void sais(const S& s, pointer sa, bool* type, pointer len,
- pointer pos, pointer lbuk, pointer sbuk, size_type n,
- size_type m) {
- type[n - 1] = false;
- for (size_type i = n - 1; i-- > 0;)
- type[i] = s[i] != s[i + 1] ? s[i] < s[i + 1] : type[i + 1];
- size_type n0 = 0;
- for (size_type i = 1; i < n; ++i)
- if (!type[i - 1] && type[i]) pos[n0++] = i;
- std::fill_n(len, n, 0);
- for (size_type p = n - 1, i = n0; i-- > 0; p = pos[i])
- len[pos[i]] = p - pos[i] + 1;
- std::fill_n(sbuk, m, 0);
- for (size_type i = 0; i < n; ++i) ++sbuk[s[i]];
- for (size_type i = 1; i < m; ++i) sbuk[i] += sbuk[i - 1];
- induced_sort(s, sa, type, pos, lbuk, sbuk, n, m, n0);
- sbuk[m - 1] = n;
- for (size_type i = 1; i < m; ++i) sbuk[i - 1] = lbuk[i];
- size_type m0 = -1;
- size_type ppos = -1, plen = 0;
- for (size_type i = 0; i < n; ++i) {
- if (len[sa[i]] == 0) continue;
- if (len[sa[i]] != plen || !substring_equal(s, sa[i], ppos, plen)) ++m0;
- plen = len[sa[i]];
- len[sa[i]] = m0;
- ppos = sa[i];
- }
- pointer s0 = sa;
- pointer sa0 = sa + n0;
- for (size_type i = 0; i < n0; ++i) s0[i] = len[pos[i]];
- if (++m0 < n0)
- sais(s0, sa0, type + n, len, pos + n0, lbuk, lbuk + n0, n0, m0);
- else
- for (size_type i = 0; i < n0; ++i) sa0[s0[i]] = i;
- for (size_type i = 0; i < n0; ++i) pos[i + n0] = pos[sa0[i]];
- induced_sort(s, sa, type, pos + n0, lbuk, sbuk, n, m, n0);
- }
- public:
- template <typename S>
- SuffixArray(const S& s, size_type n, size_type m)
- : data(std::make_unique<size_type[]>(3 * n)) {
- const auto type = std::make_unique<bool[]>(2 * n);
- const auto lbuk = std::make_unique<size_type[]>(std::max(n, m));
- const auto sbuk = std::make_unique<size_type[]>(m);
- pointer sa = data.get(), rk = sa + n, ht = rk + n;
- sais(s, sa, type.get(), rk, ht, lbuk.get(), sbuk.get(), n, m);
- for (size_type i = 0; i < n; ++i) rk[sa[i]] = i;
- for (size_type k = 0, i = 0; i < n; ++i) {
- if (rk[i] == 0) continue;
- if (k > 0) --k;
- for (size_type j = sa[rk[i] - 1], l = n - std::max(i, j); k < l; ++k)
- if (s[i + k] != s[j + k]) break;
- ht[rk[i]] = k;
- }
- this->sa = sa;
- this->rk = rk;
- this->ht = ht;
- }
- size_type suffix(size_type p) const { return sa[p]; }
- size_type rank(size_type p) const { return rk[p]; }
- size_type height(size_type p) const { return ht[p]; }
- };
- class Solution {
- public:
- string longestDupSubstring(string s) {
- const int n = s.size();
- SuffixArray sa(s.c_str(), n, 128);
- int len = 0, pos = -1;
- for (int i = 1; i < n; ++i) {
- if (sa.ht[i] > len) {
- len = sa.ht[i];
- pos = sa.sa[i];
- }
- }
- return pos == -1 ? "" : s.substr(pos, len);
- }
- };
|