Explain the working principle of the Knuth-Morris-Pratt substring search algorithm.

The Knuth-Morris-Pratt (KMP) algorithm is designed for searching a substring within a string in linear time, avoiding repeated comparisons of characters.

The main idea is to precompute an array of prefix functions (or "π-array") for the substring, which indicates how many characters matched with the beginning of the substring during a failed comparison. This allows the algorithm to shift the substring by an optimal number of positions without returning back in the original string.

Example:

• Text: "ABABDABACDABABCABAB"
• Substring to find: "ABABCABAB"

The algorithm first constructs the prefix function for the substring, then iterates through the text, comparing characters. Upon a mismatch, it uses the prefix function to determine from which character of the substring to continue the comparison, without starting over.

This ensures a complexity of O(n + m), where n is the length of the text and m is the length of the substring, making it more efficient than naive search.