Shortest Palindrome


#3 Implementation may not be able to handle the case if '#' is in string s.
Here is an implementation to remove the limitation.string rev(s.rbegin(), s.rend()); if (s == rev) return s; vector<int> lps(rev.size(), 0); int len = 0; for (int i = 1; i < rev.size(); i++) { while (len > 0 && rev[i] != s[len]) len = lps[len  1]; if (rev[i] == s[len]) len++; lps[i] = len; } return rev + s.substr(len, s.size()  len);

@JianMa Thank you for your suggestion. We tried to keep the implementation similar to the original KMP routine for easier understanding. But would surely incorporate the solution as an improvement :)

For Solution #2, why the time cost is O(NlogN) rather than o(N) when the article claims that the size of string is reduced by half each recursion?
Let T(N) indicates the time complexity of the algorithm in regard of a string of length N. T(N) = T(N/2) +O(N). By replacement, we have T(N) = O(N) + O(N/2) + O(N/4) + ... + O(1) <= O(2N) = O(N). So I think T(N) = O(N) for Solution #2.

@MITCHELLHE Thanks for the rectification. You are right, the time complexity has been calculated incorrectly and will be updated.

For solution #2, the worst timing complexity is O(n^2), although in each iteration the string is divided into 2 part, is possible the s[i:] part has very few letters or even only 1 letter. Thus T(N) = T(N1) + O(N) > O(n^2)
e.g. s = "aababababababababababa"
@MITCHELLHE @abhinavbansal0

@CONOVER yes you are right. Extremely sorry to have missed this case. Thank you for the correction :)

The algorithm to generate lookup table can be improved. There is no need to assign t = f(i1) during each iteration. t is simply pointing to the first letter outside the longest prefix. Therefore, the whole idea to do f[i] = ++t is to both assign f[i] with the right value and move t to the right position for next iteration.
f(0) = 0
for(i = 1; i < n; i++)
{
while(t > 0 && b[i] != b[t])
t = f(t1)
if(b[i] == b[t]){
f(i) = ++t;
}Should do the work.

@meame2010 said in Shortest Palindrome:
tried both the first and the second methods in Python, all time limit error.
I just tried that as well and got both accepted fine.