CareerCup

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?

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

O(N) looks impossible to me unless some constraints have not been specified here.

Yep, suffix trees are your best bet. Though I wonder if they expect you to actually CODE it during the interview. Name dropping Ukkonen's algorithm is one thing, implementing it is another…

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.