資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中最長重複子串
假設我們有一個字串S，考慮所有出現2次或更多次的重複連續子串。（這些出現可以重疊），我們需要找到長度最長的重複子串。如果沒有這樣的子串，則返回空字串。由於答案可能非常大，因此返回模10^9 + 7的結果。
因此，如果輸入為“ababbaba”，則輸出為“bab”。
為了解決這個問題，我們將遵循以下步驟：
m := 1e9 + 7
定義一個函式add()，它將接收a, b，
返回((a mod m) + (b mod m)) mod m
定義一個函式sub()，它將接收a, b，
返回((a mod m) - (b mod m) + m) mod m
定義一個函式mul()，它將接收a, b，
返回((a mod m) * (b mod m)) mod m
定義一個數組power
定義一個函式ok()，它將接收x, s，
如果x等於0，則：
返回空字串
定義一個名為hash的map
current := 0
對於初始化i := 0，當i < x時，更新（i增加1），執行：
current := add(mul(current, 26), s[i] - 'a')
hash[current] := 定義一個數組(1, 0)
n := s的大小
對於初始化i := x，當i < n時，更新（i增加1），執行：
current := sub(current, mul(power[x - 1], s[i - x] - 'a'))
current := add(mul(current, 26), s[i] - 'a')
如果count是hash的成員，則：
對於hash[current]中的所有it：
如果s從it到x - 1的子串與s從i - x + 1到x - 1的子串相同，則：
返回s從it到x - 1的子串
否則
將i - x + 1插入到hash[current]的末尾
返回空字串
在主方法中，執行以下操作：
ret := 空字串
n := S的大小
power := 定義一個大小為n的陣列並用1填充它
對於初始化i := 1，當i < n時，更新（i增加1），執行：
power[i] := mul(power[i - 1], 26)
low := 0, high := n - 1
當low <= high時，執行：
mid := low + (high - low) /2
temp := ok(mid, S)
如果temp的大小等於0，則：
high := mid - 1
否則
如果temp的大小 > ret的大小，則：
ret := temp
low := mid + 1
返回ret
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int m = 1e9 + 7;
int add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int sub(lli a, lli b){
return ((a % m) - (b % m) + m) % m;
}
int mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
vector<int> power;
string ok(int x, string s){
if (x == 0)
return "";
unordered_map<int, vector<int> > hash;
lli current = 0;
for (int i = 0; i < x; i++) {
current = add(mul(current, 26), s[i] - 'a');
}
hash[current] = vector<int>(1, 0);
int n = s.size();
for (int i = x; i < n; i++) {
current = sub(current, mul(power[x - 1], s[i - x] -
'a'));
current = add(mul(current, 26), s[i] - 'a');
if (hash.count(current)) {
for (auto& it : hash[current]) {
if (s.substr(it, x) == s.substr(i - x + 1, x)) {
return s.substr(it, x);
}
}
} else {
hash[current].push_back(i - x + 1);
}
}
return "";
}
string longestDupSubstring(string S){
string ret = "";
int n = S.size();
power = vector<int>(n, 1);
for (int i = 1; i < n; i++) {
power[i] = mul(power[i - 1], 26);
}
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
string temp = ok(mid, S);
if (temp.size() == 0) {
high = mid - 1;
} else {
if (temp.size() > ret.size())
ret = temp;
low = mid + 1;
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestDupSubstring("ababbaba"));
}輸入
"ababbaba"
輸出
bab
瀏覽量：563
