📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    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