# Share a solution using Boyer-Moore, 4ms in c++ with comments

• ``````string shortestPalindrome(string s) {
int n = s.length();
if (n < 2) return s;
string rs = s;
reverse(rs.begin(), rs.end());
int right[26]{0}, rright[26]{0}; // the last index of every character
int j, tmp, i = 0;
for (i = 0; i < n; ++i) {
right[s[i] - 'a'] = i;
rright[rs[i] - 'a'] = i;
}
i = 0;
// match s in rs
while (i < n) {
for (j = n - 1 - i; j >= 0; --j) {
if (s[j] != rs[i + j]) {
// first check the last rs[i + j] in s and move s to right by j - lastpos
// s:  aaacbaaaa  // s[5] != rs[5] , find the last rs[5] in s which is 3, so move s right by 5 - 3
// rs: aaaabcaaa
tmp = j - right[rs[i + j] - 'a'];
if (tmp <= 0) { // UPDATE: the previous method is wrong in case "aabababababaababaa" and I changed the 3 lines code below
// if the lastpos is right to j, find the next s[j] in rs and move s right to the pos
// s:    aaacbaaaa    // s[4] != rs[2 + 4] and last rs[6] in s is 8, not valid
// rs: aaaabcaaa      // so find first s[4] in rs after i + j which is the end, so move s[4] right to end
tmp = i + j + 1;
while (tmp < n && rs[tmp] != s[j]) tmp++;
tmp = tmp - i - j;
}
if (tmp <= 0) j = n - i - j;
else j = tmp;
i += j;
break;
}
}
if (j < 0) {
return rs.substr(0, i) + s;
}
}

return rs.substr(0, n - 1) + s;
}
``````

UPDATE: my previous method is wrong in case "aabababababaababaa" which is not included in test cases @1337c0d3r and I changed

``````tmp = rright[s[j] - 'a'] - i - j;
``````

to

``````tmp = i + j + 1;
while (tmp < n && rs[tmp] != s[j]) tmp++;
tmp = tmp - i - j;``````

• This solution is not good. After j becomes small enough,

``````   tmp = j - right[rs[i + j] - 'a'];
``````

have a high chance to be less than 0, and you have to perform linear search

``````   if (tmp <= 0) { // UPDATE: the previous method is wrong in case "aabababababaababaa" and I changed the   3 lines code below
``````

then.

So it's not good to only record the last position in "right". And why not just use a map for "right"?

• Yeah you are right, in the worst cases it's nearly O(n^2), and your suggestion can improve a lot which is very good.
I proposed it because I think maybe Boyer-Moore can do a better job and just offer a few commonplace remarks by way of introduction so that others like you may come up with valuable opinions.

My previous thought is to use a matrix[n][26] to save every char's first position behind i in the reversed string, and can change the linear search:
while (tmp < n && rs[tmp] != s[j]) tmp++;
to O(1).
But I found it's hard to find a worst case, and just left it simple and easy to understand.
I do believe it can be improved a lot. Thank you!

• my previous method is wrong in case "aabababababaababaa" which is not included in test cases

Thanks, I have added the test case.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.