```
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;
```