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.

smart approach 3 using KMP. One possible improvement I feel is that we might not need to build s+"#"+reverse(s) . To find longest prefix in s that matches the suffix in its reverse, like you mentioned, we keep moving s to the right and compare it to its reserve. This is very similar to general string match with one difference that when pointer in reserve string reaches end, the pointer in s is the position we look for.
So sessionally what we need is implementing KMP string match plus this logic. And of course, implementation includes building a prefix lookup table for s to speed up the matching process.

To achieve O(n) complexity you could use hashing instead of KMP to look for the greatest border of the string T = S + '#' + reverse(S). You keep two pointers L and R, and loop over i:
for(i=0; T[i] != '#'; i++){
prefixHash = (prefixHash + T[i]prime^i) % mod
suffixHash = (suffixHashprime^i + T[i]) % mod
if(prefixHash == suffixHash) border found!
}

@fiorifj sorry, there were some mistakes
To achieve O(n) complexity you could use hashing instead of KMP to look for the greatest border of the string T = S + '#' + reverse(S). You loop over i:
last = T.length()1
for(i=0; T[i] != '#'; i++){
prefixHash = (prefixHash + T[i]prime^i) % mod
suffixHash = (suffixHashprime + T[lasti]) % mod
if(prefixHash == suffixHash) border found!
}