📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!
  • google app store apple app store
    • ✖

      Question

      The Knuth-Morris-Pratt (KMP) algorithm improves upon the

      Naive approach by avoiding unnecessary re-comparisons. It achieves this by:
      A Using a hash function. Correct Answer Incorrect Answer
      B Preprocessing the text to build a suffix tree. Correct Answer Incorrect Answer
      C Preprocessing the pattern to build a "longest proper prefix which is also suffix" (LPS) array. Correct Answer Incorrect Answer
      D Always shifting the pattern by 'M' positions. Correct Answer Incorrect Answer
      E Comparing characters from right to left. Correct Answer Incorrect Answer

      Solution

      The KMP algorithm preprocesses the pattern to build an LPS array (also known as a prefix function or failure function). This array tells the algorithm how many characters to shift the pattern when a mismatch occurs, based on the longest proper prefix of the pattern that is also a suffix of the current matched portion. This avoids re-comparing characters that are known to match.

      Practice Next
      More IT Operating System Questions
      ask-question