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

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.