Given a string s, return the longest prefix of s that is not equal to s and exists as a suffix of s.
Constraints
n ≤ 100,000 where n is the length of sExample 1
Input
s = “abazfaba”
Output
“aba”
Explanation
“aba” is the longest prefix that is also a suffixExample 2
Input
s = “aaa”
Output
“aa”
Bruteforce Algorithm to Find Longest Prefix and Suffix
We can try each possible suffix and to see if it is also prefix. The time complexity is O(N^2) quadratic.
1 2 3 4 5 6 7 8 9 | string longestPrefixSuffix(string s) { if (s.empty()) return ""; for (int i = 1; i < s.size(); ++ i) { if (s.find(s.substr(i)) == 0) { return s.substr(i); } } return ""; } |
string longestPrefixSuffix(string s) {
if (s.empty()) return "";
for (int i = 1; i < s.size(); ++ i) {
if (s.find(s.substr(i)) == 0) {
return s.substr(i);
}
}
return "";
}The space complexity is O(1) constant.
Rolling Hash Algorithm to Find Longest Suffix and Prefix
We can compute the rolling hashes of each prefix and suffix. This reduces the time complexity to O(N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | string longestPrefixSuffix(string s) { int64_t mod = 1e9+7; int64_t l = 0; int64_t r = 0; int64_t p = 1; int k = 0; for (int i = 0; i < s.size() - 1; ++ i) { l = (l * 128 + s[i]) % mod; r = (r + p * s[s.size() - 1 - i]) % mod; if (l == r) { k = i + 1; } p = (p * 128) % mod; } return s.substr(0, k); } |
string longestPrefixSuffix(string s) {
int64_t mod = 1e9+7;
int64_t l = 0;
int64_t r = 0;
int64_t p = 1;
int k = 0;
for (int i = 0; i < s.size() - 1; ++ i) {
l = (l * 128 + s[i]) % mod;
r = (r + p * s[s.size() - 1 - i]) % mod;
if (l == r) {
k = i + 1;
}
p = (p * 128) % mod;
}
return s.substr(0, k);
}The space complexity is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
a WordPress rating system
350 wordsa WordPress rating system
Last Post: Teaching Kids Programming - Breadth First Search Algorithm to Determine a Univalue Binary Tree
Next Post: Teaching Kids Programming - Recursive Backtracking Algorithm to Compute the Combinations