Minimum Characters to Add at Front for Palindrome

Adding characters only at the front means the original longest palindromic prefix should remain in place; every character after it must be mirrored in front. Find that prefix length in O(n) with KMP. Form t = s + '#' + reverse(s), choosing a separator absent from the alphabet, and compute the LPS or prefix-function array. The last LPS value is the length of the longest prefix of s that is also a suffix of reverse(s), which corresponds to the longest palindromic prefix of s. The answer is n - lps[last]; to construct the palindrome, prepend the reverse of the remaining suffix. Explain why brute force checking each prefix can be O(n^2). Test already-palindromic strings, one character, no repeated characters, and separator safety. KMP computation and reversal cost O(n) time and O(n) auxiliary space. A rolling-hash alternative needs collision handling, so the prefix function is deterministic.