Amazon Interview Question
SDE1sCountry: United States
The only solution possible for LC substring between two strings is : Manacher’s Algorithm
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(string s) {
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
int n = T.length();
int *P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n-1; i++) {
int i_mirror = 2*C-i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
delete[] P;
return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}
Source: Refer to leetcode.com
Here good description of the algo:
books.google.pl/books?id=4j_GfM0tyPUC&pg=PA60&dq=longest+common+substring+problem&hl=pl&sa=X&ei=v1_QUt-gHqrV4ATPtoGQDQ&ved=0CDUQ6AEwAA#v=onepage&q=longest%20common%20substring%20problem&f=false
Note building generalized suffix tree can be done using ukkonen's algorithm in linear time.
Is it really expected for one to know Ukonnen and how it can be solved using suffix tree or suffix array? Wouldn't a simple dynamic n*m approach be enough for an interview?
- Anonymous January 10, 2014