KMP in Interview

After some questions about basic knowledge of Java, interviewer give Amy the last question: how to find the ‘Longest common substring between two string’ efficiently?

Amy thinks for a while and comes up with the DP solution which depends on the core equation of

// longest common suffix
dp[i][j] = m[i] == n[j] ? dp[i-1][j-1]+1 : 0

max(dp[1..x][1..y])

Interviewer check the solution and said, “It’s a good solution. But it’s time complexity is O(n^2) and space complexity is also O(n^2). Can you come up with better algorithm?”

Amy ponder the question again and suddenly the KMP algorithm dawn on her.

What is KMP

"The KMP algorithm is a very efficient string comparison algorithm which save the time by extra pre-process. When we compare string in common way, we do like this: when a mismatch happens, we reset start point to old_position + 1:

...xxx...xxy
   xxy..
     ⇑
     mismatch

...xxx...xxy
    xx..
    ⇑
    restart with head + 1

“But with the help of KMP pre-computed table, we can move more aggressive to the new beginning.” Amy said.

...xxx...xxy
   xxy..
     ⇑
     mismatch

...xxx...xxy
         xxy.
           ⇑
          restart with head + n

How it Works

“So how could move more than one index?” The interviewer wants more details.

"Saying we have a string which is the pattern to match. Then, we have a target to find pattern. After some normal comparisons, the first mismatch happens.

012345
abcabc...   <- pattern
abcaba...   <- target
     ⇑
     mismatch

"Now, because we have analyzed pattern string, we know that the first five character of pattern/target has same prefix and suffix – ‘ab’. So we can move pattern direct to the suffix position rather than just one.

012345
   abcabc...   <- pattern
abcaba...      <- target
     ⇑
     mismatch

"Then, we can continue to compare the last mismatch position (index 5 in our case). The core is the same prefix and suffix of already matched part.

-------------
///       ///       <- pattern
-------------
------------------
///       /// ...
------------------
          -------------
          ///       ///   <- pattern moved
          -------------

"One more thing is we have to use longest same prefix and suffix¹. Because if we move directly to shorter suffix position (move farther² than longest suffix), we just skip some possible match – the one start from longest suffix position.

“From the simulation, we can see that, the longer the suffix/prefix is, the less we can move. Or in more programming way, we move matchLen - table[index-1] position.” Amy finished.

Table Computation

“Great explanation. But what’s the complexity of your KMP solution?” The interviewer added.

“If we don’t take the pre-process of pattern string table, the time complexity would be O(n), where n is the length of target string. In our Longest Common Substring problem, we should add table computation time, which should be the O(m). All in all, the time should be O(m+n).” Amy answered.

“Can you show me how to build the table?”

"Yes. It is kind of DP thought. If we already knew the longest prefix and suffix at index i-1, and we have the same char at next suffix position (i) and next prefix index (lastPrefix, i.e. table[i-1]), we can get the answer at index i easily (lastPrefix+1). The problem is when new suffix not match.

------------
///x    ///x
------------
   ⇑       i
lastPrefix

"If suffix can’t extend, we have to find a shorter³ prefix in A which is the same with A''s suffix as the definition said. Because A is the same with A', we can just find a same prefix and suffix pair in A (as following diagram shows). Using contradiction method, we can prove that the repeated substring (// in diagram) is the longest proper prefix and suffix and the length is stored in table[lastPrefix-1]. Recursively, the problem become: whether the char at table[lastPrefix-1] is same with char at i.

------------------------
|// A  |       | A' //|x
------------------------
        ⇑              i
lastPrefix

-----

table[lastPrefix-1]
   ⇓
------------------------
|//  //|       |//  //|x
------------------------
      ⇑                i
lastPrefix-1

-----

------------
//?      //x
------------
  ⇑       i
lastPrefix

“Pseudo-code is like the following.” Amy finished.

if (cs[i] == cs[lastPrefix]) {
    res[i] = res[i - 1] + 1;
    lastPrefix++;
} else {
    int lastPrefix = res[i - 1] - 1;  
    while (lastPrefix >= 0 && cs[i] != cs[res[lastPrefix]]) {  
        lastPrefix = res[lastPrefix] - 1;  
    }  
    if (lastPrefix >= 0) {  
        res[i] = res[lastPrefix] + 1;  
    }
}

---

When to Use

Postscript: KMP is a very powerful string comparison algorithm, if we are meet O(n) string comparison problem, we may try to use KMP.

• String comparison: find string in another
• Longest common substring
• Longest palindrome start from head or end at tail: can you come up with the solution that use KMP to solve?

Written with StackEdit.

---

1. Longest same prefix and suffix except that string itself, otherwise, we can’t move to next meaningful position. ↩︎

2. If you are confused, you may like to draw some simple black boxes to represent prefix and suffix, then move it and you will see. ↩︎

3. It must be shorter, otherwise the table[i-1] is invalid, where can be proved by contradiction. ↩︎