ЁЯУв Too many exams? DonтАЩt know which one suits you best? Book Your Free Expert ЁЯСЙ call Now!

    Question

    In the Knuth-Morris-Pratt (KMP) algorithm, the Longest

    Proper Prefix Suffix (LPS) array lps[] is crucial. When pat[i] and pat[len] match, len is incremented and lps[i] is set to len. What happens when pat[i] and pat[len] *do not* match and len is not 0? void computeLPSArray(char* pat, int M, int* lps) { ┬а ┬а int len = 0; ┬а ┬а lps[0] = 0; ┬а ┬а int i = 1; ┬а ┬а while (i < M) { ┬а ┬а ┬а ┬а if (pat[i] == pat[len]) { ┬а ┬а ┬а ┬а ┬а ┬а len++; ┬а ┬а ┬а ┬а ┬а ┬а lps[i] = len; ┬а ┬а ┬а ┬а ┬а ┬а i++; ┬а ┬а ┬а ┬а } else { // (pat[i] != pat[len]) ┬а ┬а ┬а ┬а ┬а ┬а if (len != 0) { ┬а ┬а ┬а ┬а ┬а ┬а ┬а ┬а _________; // Line to complete ┬а ┬а ┬а ┬а ┬а ┬а } else { // if (len == 0) ┬а ┬а ┬а ┬а ┬а ┬а ┬а ┬а lps[i] = 0; ┬а ┬а ┬а ┬а ┬а ┬а ┬а ┬а i++; ┬а ┬а ┬а ┬а ┬а ┬а } ┬а ┬а ┬а ┬а } ┬а ┬а } }
    A len = 0; Correct Answer Incorrect Answer
    B len = lps[len - 1]; Correct Answer Incorrect Answer
    C i++; Correct Answer Incorrect Answer
    D lps[i] = len; Correct Answer Incorrect Answer
    E len = len - 1; Correct Answer Incorrect Answer

    Solution

    тАв Concept: The Knuth-Morris-Pratt (KMP) algorithm uses a precomputed Longest Proper Prefix Suffix (LPS) array to efficiently search for a pattern within a text. The LPS array lps[i] stores the length of the longest proper prefix of pat[0...i] that is also a suffix of pat[0...i]. тАв Code Analysis: o The while loop builds the lps array. o When pat[i] == pat[len], len is incremented, and lps[i] is set to the new len. o When pat[i] != pat[len] and len != 0, it means the current character pat[i] does not extend the current prefix-suffix match. We need to "fall back" to a shorter possible prefix-suffix match. тАв Explanation of Correct Answer (B): len = lps[len - 1]; o When pat[i] does not match pat[len], and len is not 0, it means we had a prefix of length len that matched a suffix. Since pat[i] doesn't extend this match, we look for the next shortest proper prefix of pat[0...len-1] that is also a suffix of pat[0...len-1]. The length of this next shortest match is precisely stored in lps[len - 1]. By setting len = lps[len - 1], we effectively shift our comparison point in the pattern to try and find a shorter matching prefix.

    Practice Next
    More IT Operating System Questions
    ask-question