本题的平凡解法很容易想到，既然要求最长的，那从最大长度向下遍历不就好啦，考虑到这里长度数轴具有二段性，什么是二段性呢，可以简单理解为以最大长度为分界点，左侧数轴长度都存在重复串，右侧数轴都不存在重复串，By the way突然想到这与高数中幂级数判别收敛半径的阿贝尔定理似乎有异曲同工之妙hhh，由二分确定试探长度后，接下来就是判断在该长度下是否存在重复子串，如果采用滑动窗口的思想逐一遍历每个子串再用set哈希映射来判断重复，则复杂度会与试探长度有关，大概是O(n*subs_len)，subs_len为试探长度，在输入很长的情况下会导致超时，此时可以用“串亦为数”的思想进行优化，也就是采用Karp-Robin算法，利用O(n)的预处理哈希数组，它可以让我们在O(1)时间内计算出子串的哈希值，就像在一个数字数组中执行滑动窗口！因此整体算法复杂度为预处理O(n)+二分O(nlogn)合起来是O(nlogn)。

当然，本题更优的解法是采用后缀数组，考虑如果存在两个子串相同，那么把这两个串一直延伸到串的末尾，就能得到两个具有公共前缀的后缀子串，那么由此目标也就变成求后缀间的最长公共前缀，而具有最长公共前缀的两个后缀字典排序时位置一定是紧挨着的，因此可以利用后缀数组来求得最长公共前缀，当然构造后缀数组有比较简单的倍增法，经过基数排序优化后其复杂度为O(nlogn)，如果采用稍复杂的SA-IS构造法，复杂度可以进一步优化至O(n)，当然因为SA-IS代码量过长且不够简洁易懂文中还是采用倍增法构造（emm也有可能是因为鼠鼠研究不明白SA-IS）。

题面

• 题目描述

  给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

  返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

• 样例

  示例 1：

  输入：s = "banana"
  输出："ana"

  示例 2：

  输入：s = "abcd"
  输出：""

• Tips

  • 2 <= s.length <= 3 * 10^4
  • s 由小写英文字母组成

O(nlogn) Karp-Robin + 二分

补充一个常用的区间哈希公式，更方便下文代码中计算当前窗口的哈希值，由于使用了无符号自然溢出公式中就没有加上取余操作了
Hash[L----R]=(Hash[R]-Hash[L-1]*base[R-L+1])

class Solution {
public:
    int s_len; //输入s的长度
    int P = 2333333; //KR算法选取的进制数,一般取1313131或2333333即可
    string longestDupSubstring(string s) {
        s_len = s.length();
        //unsigned long long可以自动取模，也可以用一个大质数实现取模操作
        vector<unsigned long long> base(s_len + 1); //base预记录P的base数组下标次方
        base[0] = 1;
        vector<unsigned long long> strhash(s_len + 1); //strhash预记录串s从开头到各个位置的哈希值,注意这里strhash[0]为0,表示空串哈希值
        //即s[0]的哈希值为strhash[1],从s[0]到s[s_len-1]的哈希值为strhash[s_len],这也是为什么strhash数组长度要+1的原因
        for (int i = 0; i < s_len; i++) {
            base[i + 1] = base[i] * P;
            strhash[i + 1] = strhash[i] * P + s[i];
        }
        string ans = "";
        int l = 1, r = s_len - 1; //重复子串的可能长度为1 ~ len-1
        while (l <= r) {
            //二分,这里二分的目的是尽快找到临界点即最长的重复串长度
            int mid = (l + r) >> 1;
            int pos = check(mid, strhash, base);
            if (pos) {
                //返回位置不为false那么临界点在mid或者mid右边,mid的情况已经计入结果内了,因此直接令左端等于mid+1继续判断即可
                if (ans.length() < mid)
                    ans = s.substr(pos, mid);
                l = mid + 1;
            } else
                r = mid - 1;
        }
        return ans;
    }

    //判断当前长度下是否存在重复子串
    int check(int subs_len, vector<unsigned long long> &strhash, vector<unsigned long long> &base) {
        unordered_set<unsigned long long> set; //字符串哈希值映射集
        unsigned long long curhash; //当前子串哈希值
        for (int i = 1; i + subs_len - 1 <= s_len; i++) {
            curhash = strhash[i + subs_len - 1] - strhash[i - 1] * base[subs_len]; //上文公式
            if (set.contains(curhash)) //若存在重复串则返回位置,注意因为strhash与s错开了一位,所以位置要-1
                return i - 1;
            set.insert(curhash);
        }
        return false;
    }
};

O(nlogn) 后缀数组（倍增法+基数排序优化）

class Solution {
public:
    string longestDupSubstring(string s) {
        int s_len = s.length();
        int m = 128;
        //改为1-index,使代码结构简洁化
        s = " " + s;
        //x保存下标位置后缀排名,首次初始化为ASCII值,当sa构造算法完成后x可以视为rk排名数组
        vector<int> x(s_len + 1, 0);
        //y是辅助数组,在每一轮倍增中保存经过第二关键字排序后的下标,为后续的第一关键字排名做准备
        vector<int> y(s_len + 1, 0);
        //c是计数排序中的辅助数组
        vector<int> c(max(s_len+1,m+1), 0);
        //sa即后缀数组,目标是通过倍增得到最终的sa
        vector<int> sa(s_len + 1, 0);
        //rk即排名数组
        //height高度数组用于保存最长前缀LCP
        vector<int> height(s_len + 1, 0);

        //利用计数排序初始化x和sa
        for (int i = 1; i <= s_len; i++) {
            x[i] = s[i];
            c[x[i]]++;
        }
        for (int i = 2; i <= m; i++)
            c[i] += c[i - 1];
        for (int i = s_len; i >= 1; i--)
            sa[c[x[i]]--] = i;

        //基于计数排序的双关键字基数排序
        //k为每一轮后缀的长度
        for (int k = 1; k <= s_len; k <<= 1) {
            //cnt作为y数组位置游标
            int cnt = 0;
            //先将后缀尾部不足k(即该后缀的第二关键字不存在的情况)的位置加入y数组,也就是按第二关键字排序的最小值的位置。
            for (int i = s_len - k + 1; i <= s_len; i++) {
                y[++cnt] = i;
            }
            //对于尾部充足的后缀(即其第二关键字存在也就是i+k存在)则判断前面是否存在能作为第一关键字的位置,存在则将第一关键字位置加入数组即s[i]-k
            //如此一来我们便得到了按照第二关键字排序后的下标数组y
            for (int i = 1; i <= s_len; i++) {
                if (sa[i] > k) {
                    y[++cnt] = sa[i] - k;
                }
            }
            //清空数组c准备进行计数排序
            fill_n(c.begin()+1, m, 0);
            //利用计数排序,根据第一关键字x[y[i]]对后缀y[i]进行排序,倒序保证稳定性,并更新sa数组
            for (int i = 1; i <= s_len; i++)
                c[x[i]]++;
            for (int i = 1; i <= m; i++)
                c[i] += c[i - 1];
            for (int i = s_len; i >= 1; i--)
                sa[c[x[y[i]]]--] = y[i];
            //更新新长度下x数组中的排名值
            y = x;
            cnt = 1;
            x[sa[1]] = cnt;
            for (int i = 2; i <= s_len; i++) {
                //前一个后缀的第二关键字排名值
                int prev_second = sa[i - 1] + k <= s_len ? y[sa[i - 1] + k] : 0;
                //当前后缀的第二关键字排名值
                int curr_second = sa[i] + k <= s_len ? y[sa[i] + k] : 0;
                //若第一关键字和第二关键字都相同则排名相同,否则排名递增
                if (y[sa[i]] == y[sa[i - 1]] && curr_second == prev_second)
                    x[sa[i]] = cnt;
                else
                    x[sa[i]] = ++cnt;
            }
            // 若所有后缀都有不同排名,则排序结束
            if (cnt == s_len)
                break;
            // 更新m为当前排名数目
            m = cnt;
        }
        //构建height数组
        //height[i]表示sa[i]和sa[i-1]两个相邻后缀的最长公共前缀长度
        int k = 0;
        for (int i = 1; i <= s_len; i++) {
            //若当前后缀在sa数组中排第一,则没有前一个后缀,跳过
            if (x[i] == 1) {
                height[x[i]] = 0;
                continue;
            }
            //j为当前后缀i的前一个后缀在原串中的起始位置
            int j = sa[x[i] - 1];
            //若 k > 0,尝试k-1长度的公共前缀
            if (k)
                k--;
            //逐个字符比较,直到不相同或到达串尾
            while (i + k <= s_len && j + k <= s_len && s[i + k] == s[j + k]) {
                k++;
            }
            height[x[i]] = k;
        }
        int idx = -1, max = 0;
        for (int i = 1; i <= s_len; i++) {
            if (height[i] > max) {
                max = height[i];
                idx = sa[i];
            }
        }
        return max == 0 ? "" : s.substr(idx, max);
    }
};