I'm posting my C++ code for LeetCode's Longest Duplicate Substring. If you have time and would like to review, please do so. Thank you!
Problem
Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)
Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is "".)
Example 1:
- Input: "banana"
- Output: "ana"
Example 2:
- Input: "abcd"
- Output: ""
Note:
- 2 <= S.length <= 10^5
- S consists of lowercase English letters.
Accepted C++
class Solution {
private:
const int prime = 19260817;
const int a_decimal = 65;
const int char_size = 26;
std::string res = "";
std::vector<int> exponent;
// Wikipedia
// The Rabin–Karp algorithm or Karp–Rabin algorithm is a string - searching algorithm that uses hashing to find an exact match of a pattern string in a text.
// It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern,
// and then checks for a match at the remaining positions.
const std::string rabin_karp_search(const int length, const string& base) {
if (length == 0) {
return "";
}
std::unordered_map<int, vector<int>> hash_map = unordered_map<int, vector<int>>(); // hash memorization
long long curr = 0; // current hash
int index;
for (index = 0; index < length; index++) {
curr = ((curr * char_size) % prime + (base[index] - a_decimal)) % prime;
}
hash_map[curr] = std::vector<int>(1, 0);
for (index = length; index < base.length(); index++) {
curr = ((curr - (long long) exponent[length - 1] * (base[index - length] - a_decimal)) % prime + prime) % prime;
curr = (curr * char_size + (base[index] - a_decimal)) % prime;
if (hash_map.find(curr) == hash_map.end()) {
hash_map[curr] = std::vector<int>(1, -~index - length);
} else {
for (const auto iter : hash_map[curr]) {
if (std::strcmp((base.substr(iter, length)).data(), base.substr(-~index - length, length).data()) == 0) {
return base.substr(iter, length);
}
}
hash_map[curr].push_back(-~index - length);
}
}
return "";
}
// Wikipedia
// binary search is a search algorithm that finds the position of a target value within a sorted array.
// Binary search compares the target value to the middle element of the array.
// If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half,
// again taking the middle element to compare to the target value, and repeating this until the target value is found.
// If the search ends with the remaining half being empty, the target is not in the array.
const std::string get_longest_binary_search(std::string base_string, std::string res) {
int lo = 0;
int hi = base_string.length();
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
std::string temp = rabin_karp_search(mid, base_string);
if (temp.length() == 0) {
hi = mid - 1;
} else {
if (temp.length() > res.length()) {
res = temp;
}
lo = -~mid;
}
}
return res;
}
public:
const std::string longestDupSubstring(const std::string base_string) {
res = "";
exponent = std::vector<int>(base_string.length(), 1);
int index;
for (index = 1; index < base_string.length(); index++) {
exponent[index] = (exponent[index - 1] * char_size) % prime;
}
return get_longest_binary_search(base_string, res);
}
};
LeetCode Solution in Java with additional comments (Not for review)
class Solution {
/*
Rabin-Karp with polynomial rolling hash.
Search a substring of given length
that occurs at least 2 times.
Return start position if the substring exits and -1 otherwise.
*/
public int search(int L, int a, long modulus, int n, int[] nums) {
// compute the hash of string S[:L]
long h = 0;
for(int i = 0; i < L; ++i) h = (h * a + nums[i]) % modulus;
// already seen hashes of strings of length L
HashSet<Long> seen = new HashSet();
seen.add(h);
// const value to be used often : a**L % modulus
long aL = 1;
for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;
for(int start = 1; start < n - L + 1; ++start) {
// compute rolling hash in O(1) time
h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;
h = (h + nums[start + L - 1]) % modulus;
if (seen.contains(h)) return start;
seen.add(h);
}
return -1;
}
public String longestDupSubstring(String S) {
int n = S.length();
// convert string to array of integers
// to implement constant time slice
int[] nums = new int[n];
for(int i = 0; i < n; ++i) nums[i] = (int)S.charAt(i) - (int)'a';
// base value for the rolling hash function
int a = 26;
// modulus value for the rolling hash function to avoid overflow
long modulus = (long)Math.pow(2, 32);
// binary search, L = repeating string length
int left = 1, right = n;
int L;
while (left <= right) {
L = left + (right - left) / 2;
if (search(L, a, modulus, n, nums) != -1) left = L + 1;
else right = L - 1;
}
int start = search(left - 1, a, modulus, n, nums);
return S.substring(start, start + left - 1);
}
}
Reference
LeetCode is a platform only for interviewing and competitive programming. On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.
