给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）
2 <= S.length <= 10^5
S 由小写英文字母组成。
示例1
输入：“banana”
输出：“ana”
示例2
输入："abcd"
输出：""
1. 自己的解题思路
首先这个题如果不考虑复杂度，那么显然暴力遍历所有长度的子串判断是否有重复直到无重复是可以解决这个问题的。但是这是一道难度为困难的题，以及题目中S的长度可以高达10^5，时间复杂度会爆炸，肯定不是期望的解法。复杂度的来源主要是子串的长度L的范围是1 ~ S.length() - 1，这是外循环。每一个长度L，需要以其长度为窗口，得到S.length() - L + 1个子串，这么多数量的子串，需要对比是否存在重复的子串。
我自己想的降低这个问题的复杂的方法是来源于动态规划解最长公共子串的问题思路，就是我在进行长度为L的子串匹配的前提是这两个子串在L-1处是相等的。所以前L-1个字符就不需要比较，只需要对比最后一个字符是否相等。如在L=2的时候，index=1和index=3开始长度为2的子串是相等的，那么只要S[1 + 2] == S[3 + 2]，L的长度就可以扩展1。在index=2和index=4的位置上的在L=2时是相等的，但是S[2 + 2] ！= S[4 + 2]，因为S[6]已经超出了字符串的范围。假设S[6]存在，但是不同的话，那么以2和4为起点的字符串不能扩展到L+1 = 3的长度，因此在下一轮处理前，这两个位置开始的子串不可能匹配了。通过不断拓展L的长度，直到再也没有两个子串可以继续拓展了，就得到了子串的最长长度。
这种解法能在一定程度上降低串匹配的时间复杂度，因为不合适的子串早早被排除在外，只有能继续拓展的子串才会被留下来，而且每一次拓展只需要比较相应子串的一个字符对，对已经比较过的不需要重复比较。于是我写出了如下代码，简单的用例都过了，但是最终还是运行时间超时。考虑超时的原因主要是对于一个很长的字符串，在L很小的时候，势必有很多的匹配的字符串对，他们之间需要两辆对比判断是丢弃还是可以继续拓展。然后L需要从小到大一次拓展，外层循环需要进行很多次，内层循环在L很小的时候时间复杂度也很高。在最坏情况下时间复杂度还是在n*O(n^2)的量级，因此时间复杂度还需要改进。
class Solution {
public:
string longestDupSubstring(string S) {
vector<vector<int>> table(26);
int len = S.length();
for (int i = 0; i < len; i++) {
table[S[i] - 'a'].push_back(i);
}
vector<vector<int>> pairs;
for (int i = 0; i < 26; i++) {
int numOfSame = table[i].size();
if (numOfSame > 1) {
for (int a = 0; a < numOfSame; a++) {
for (int b = a + 1; b < numOfSame; b++) {
vector<int> tmp;
tmp.push_back(table[i][a]);
tmp.push_back(table[i][b]);
pairs.push_back(tmp);
}
}
}
}
if (pairs.empty())
return "";
int result = 1;
int start = 0;
while (!pairs.empty()) {
start = pairs[0][0];
for (auto it = pairs.begin(); it != pairs.end(); ) {
int index1 = (*it)[0] + result;
int index2 = (*it)[1] + result;
if (index1 < len && index2 < len && S[index1] == S[index2]) {
it++;
}
else {
it = pairs.erase(it);
}
}
result++;
}
string sub = S.substr(start, result - 1);
return sub;
}
};
2. 官方解法：二分查找 + Rabin-Karp 字符串编码
官方解法也是在暴力解法的时间复杂度方向进行改进。但是改进是两个方面的：首先L的拓展不是逐一增减，而是采用二分搜索的方式，将O（n）的复杂度转换成O(logn)；除此之外，子串的匹配问题采用了Rabin-Karp编码方式使得O(L * n)的字符串匹配复杂度减小到平均O(1 * n)。最终的时间复杂度只有O(n * logn)。
在看懂了题解的思路之后我开始尝试自己完成这段代码，然而困难难度的题果然不一样，即使我照着这个思路写还是遇到了很多问题。
这里面有超出时间限制和执行出错两种结果分别是由于算法复杂度过高已经大数溢出问题造成的。复杂度过高的原因我一直试图定位，我觉得可能是求幂的地方出问题，所以用了快速幂的方法。但是最后才发现其实是在用vector存每个窗口的字符串的时候会存在很大的问题。对比标准答案，人家在遍历整个字符串的过程中是用java里的hashset来存储的，把查找过程O(n^2)的复杂度降低到了O(n).C++标准里没有hashset，所以我最后用的是set，复杂度就是nlog(n)，因此可以看到最后C++的提交结果比java的提交结果还是大很多。
另一个溢出的问题在Rabin-Karp算法中是需要注意的就是在计算的每一步可能溢出的地方，都要小心的进行取模。模数取多大是个数学上的问题，题解中说这里需要取到2^32次方才能保证只需要比较编码是否相等就能判断字符串是否匹配。我试了试2^31次方，确实结果就不对的。其实模数可以取小一点，那就需要在模相同的情况下再比较两个模对应的子串是否匹配。由于用set存放编码的时候并没有记录出现这个编码的索引位置，所以没有办法比较字符串。当然可以用map来对应的存编码和索引应该可以解决这个问题，但是这里我并没有改，而是取了模为2^32次方来保证匹配。模太大带来的一个问题就是容易溢出，特别是在我采取快速幂的求幂方法时，我存储数字的位数也就64位，当两个不超过的2^32的数的乘积还是会超过所能存储的最大值。因此最后这一题也没办法用快速幂来做，而是采取了普通每一步求幂取模的方法。
class Solution {
public:
//子串匹配问题,在长度L的子串中，存在重复的就返回重复的子串的位置index，否则返回-1
int RabinKarp(vector<int>& nums, string& S, int L, long long mod) {
set<long long> table;
long long code = 0;
//计算第一个窗口的字符串编码后的值
for (int i = 0; i < L; i++) {
code = code * 26 + nums[i];
code = code % mod;
}
table.insert(code);
long long aL = 1;
for(int i = 0; i < L - 1; i++){
aL = (aL * 26) % mod;
}
//窗口一次向后移动，更新code的值
for (int i = L; i < nums.size(); i++) {
int firstNum = nums[i - L];
long long num = (firstNum * aL) % mod;
code = ((code - num + mod) % mod * 26) % mod + nums[i];
code = code % mod;
auto it = table.find(code);
if (it == table.end())
table.insert(code);
else {
return i - L + 1;
}
}
return -1;
}
string longestDupSubstring(string S) {
//该函数主要实现L的二分，把串匹配的操作交个另一个函数
int n = S.length();
long long mod = (long long)pow(2, 32);
vector<int> nums(n, 0);
for (int i = 0; i < n; i++) {
nums[i] = S[i] - 'a';
}
int left = 1;
int right = n;
int L;
while (left != right) {
L = left + (right - left) / 2;
if (RabinKarp(nums, S, L, mod) != -1) {
left = L + 1;
}
else
right = L;
}
int start = RabinKarp(nums, S, left - 1, mod);
if (start == -1)
return "";
return S.substr(start, left - 1);
}
};
3. 总结
困难的题对算法效率的要求真的挺高的，平时在数据结构的使用上不太注意，因为时间复杂度不是瓶颈，基本上是能用vector就用vector了。但是在这种情况下，需要极度优化时间效率，即使使用了标准的解法，但是实现上不太注意选取数据结构带来的影响，导致整个算法的复杂度依然由于这个瓶颈降不下来，真的是很遗憾的。
