The key is to find a way to do high efficient string matching.

Most solution are based on O(N) space KMP algo. Here I present another O(1) space solution.

Define a string's polynomial function as

```
Hash(s) = (c0*p^n + c1*p^(n-1) + ... cn) % m
```

Therefore, it's O(1) to update the hash value when modify front or tail character.

To demonstrate how does it work, let's play with an input like 'babcd'.

Firstly, an O(N) Initialization

```
forward = hash('babcd')
reverse = hash('dcbab')
```

Then we remove the tail from forward and head from reversed, update the hash value.

```
Iteration 1: hash('babcd') != hash('dcbab')
Iteration 2: hash('babc') != hash('cbab')
Iteration 3: has('bab') == hash('bab')
```

Each iteration is O(1), so the overall complexity is O(N). And we only used two variables here:)

```
class Solution:
# @param {string} s
# @return {string}
def shortestPalindrome(self, s):
prime = 7
modular = 1000
length = len(s)
forward = reverse = 0
power = 1
for i in range(length):
forward = (forward * prime + ord(s[i])) % modular
reverse = (reverse * prime + ord(s[length - i -1])) % modular
power = power * prime % modular if i > 0 else power
forward_power = 1
for i in range(len(s)):
if forward == reverse:
tmp = s[:len(s)-i]
if tmp == tmp[-1::-1]:
return s[len(s)-i:][-1::-1] + s
pass
# Remove tail from forward
forward -= ord(s[len(s)-i-1]) * forward_power % modular
forward = forward + modular if forward < 0 else forward
forward_power *= prime
# Remove head from reverse
reverse -= ord(s[len(s)-i-1]) * power % modular
reverse = reverse + modular if reverse < 0 else reverse
reverse = reverse * prime % modular
return s[::-1] + s[1:]
```