algorithm - Minimum number of characters to be inserted at the end of a string to make it a palindrome -

the question this--

we have find minimum number of characters inserted at end of string make palindrome.

so, in efforts problem, figured equivalent finding largest palindromic substring suffix of string.

i in o(n^2) looking o(n) solution possible using modified kmp. please me figure out.

i have approach uses hashing posted answer here.

you can indeed use kmp. can compute prefix function reversed string, , iterate initial string left right:

kmp computes function prefix[i] = longest prefix of string suffix of string[1..i]

however, want know the longest suffix of our string prefix of reversed string. why? if have:

15232 => reverse = 23251 

then longest suffix of string prefix of reversed string 232. palindrome, , lets find you're asking because suffix of string overlaps prefix of reversed string if 2 palindromes.

you have cases:

prefix[i] = length - => can palindrome of              length 2*prefix[i] centered @ , i+1  prefix[i] = length - + 1 => can palindrome of             length 2*prefix[i] - 1 centered @  prefix[i] < length - => can't have palindrome, ignore position 

so suffices compute prefix function of kmp algorithm.