目錄

最長重復(fù)子串

C++代碼

---

最長重復(fù)子串

1044. 最長重復(fù)子串

給出一個字符串?S，考慮其所有重復(fù)子串（S?的連續(xù)子串，出現(xiàn)兩次或多次，可能會有重疊）。

返回任何具有最長可能長度的重復(fù)子串。（如果?S?不含重復(fù)子串，那么答案為?""。）

示例 1：

輸入："banana" 輸出："ana"

示例 2：

輸入："abcd" 輸出：""

提示：

2 <= S.length <= 10^5

S?由小寫英文字母組成。

方法一：二分查找 + Rabin-Karp 字符串編碼
分析

我們可以把這個問題分解成兩個子問題：

從 1 到 N 中選取子串的長度 L；

檢查字符串中是否存在長度為 L 的重復(fù)子串。

子任務(wù)一：二分查找

解決子問題一的最簡單的方法是，我們從 L = N - 1 開始，依次遞減選取子串的長度，并進(jìn)行判斷。如果發(fā)現(xiàn)存在長度為 L 的重復(fù)子串，就表示 L 是最長的可能長度。

但我們發(fā)現(xiàn)，如果字符串中存在長度為 L 的重復(fù)子串，那么一定存在長度為 L0 < L 的重復(fù)子串（選取長度為 L 的重復(fù)子串的某個長度為 L0 的子串即可），因此我們可以使用二分查找的方法，找到最大的 L。

子任務(wù)二：Rabin-Karp 字符串編碼

我們可以使用 Rabin-Karp 算法將字符串進(jìn)行編碼，這樣只要有兩個編碼相同，就說明存在重復(fù)子串。對于選取的長度 L：

使用長度為 L 的滑動窗口在長度為 N 的字符串上從左向右滑動；

檢查當(dāng)前處于滑動窗口中的子串的編碼是否已經(jīng)出現(xiàn)過（用一個集合存儲已經(jīng)出現(xiàn)過的編碼）；

若已經(jīng)出現(xiàn)過，就說明找到了長度為 L 的重復(fù)子串；

若沒有出現(xiàn)過，就把當(dāng)前子串的編碼加入到集合中。

C++代碼

class Solution { public: //檢查是針對存在重復(fù)子串 還是發(fā)生了哈希沖突bool check_hash(string& s, pair<int, int>& a, pair<int, int> b) { //查看是否是真重復(fù)子串還是因為發(fā)生哈希碰撞而導(dǎo)致哈希值相同for (int i = a.first, j = b.first; i != a.second && j != b.second; ++i, ++j) {if (s[i] != s[j]) return false;}return true;}//檢查字符串s中是否存在長度為len的重復(fù)子串，如果有則返回該子串，否則返回空字符串string check(string& s, int len){int base = 26;//二十六個字母對應(yīng)二十六進(jìn)制int mod = 1000007;//取模 避免哈希沖突int num = 0;for(int i = 0; i < len; i++)//計算出第一個len長度的哈希映射值num = (num * base + s[i] - 'a')%mod;unordered_map<int, pair<int, int>> seen;//存儲的是哈希映射值及對應(yīng)的坐標(biāo)seen.insert({num, {0, len - 1}});int al = 1;//根據(jù)公式 計算出常數(shù)a的len次方for(int i = 1; i <= len; i++)al = (al * base)%mod;//遍歷字符串 計算每一個長度為len的子串的哈希映射值for(int i = 1; i < s.size() - len + 1; i++){//計算長度為len的子串的哈希映射值num = num * base - ((s[i-1] - 'a') * al)%mod;while(num < 0) num += mod;num = (num + (s[i + len - 1] - 'a'))%mod;//查找是否有重復(fù)的子串if(seen.count(num))if(check_hash(s, seen[num], {i, i + len - 1}))return s.substr(i, len);//如果是真的存在而不是因為哈希沖突，就返回這個子串seen.insert({num, {i, i + len - 1}});//如果是哈希沖突 就插入}return "";}//返回字符串s最長重復(fù)子串string longestDupSubstring(string s) {int m = s.size();int left = 0, right = m;string res = "";while(left < right){int mid = left + (right - left)/2;//二分法找到最長重復(fù)子串string tmp = check(s, mid);if(!tmp.empty()){//如果存在重復(fù)子串，就保存下來最長的一個重復(fù)子串res = tmp.size() > res.size() ? tmp : res;left = mid + 1;}elseright = mid;}return res;} };

總結(jié)

以上是生活随笔為你收集整理的最长重复子串(Rabin-Karp算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。