資料結構與演算法(A)

(5 points) Consider a string of length $n$, e.g., cbaabcba. We want to add the smallest number of characters to the front of the string to make it a palindrome, e.g., abcbaabcba. This problem can be solved by first concatenating the string with its inverse with a delimiter #, e.g. cbaabcba#abcbaabc. Then, run the pre-processing routine of the Knuth-Morris-Pratt algorithm on the new string $s_0 s_1 \cdots s_{2n}$ of length $(2n + 1)$ to get a failure function $f_s(j)$, which computes the length of the longest prefix of the string $s_0 s_1 \dots s_j$ that is also a suffix. After running the pre-processing algorithm, how can we calculate the smallest number of characters that should be added to the front of the original string to make a palindrome?