# Another O(n) time & O(n) space solution using hashes (Rabin-Karp algorithm)

• Surprisingly, I didn't find solution with hashes, so I decided to share it

``````class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();

if (n < 2) {
return s;
}

vector<unsigned int> hashes(n);
vector<unsigned int> reverse_hashes(n);

const unsigned int base = 31;
unsigned int hash = 0;
unsigned int power = 1;

vector<unsigned int> powers(n);

for (int i = 0; i < n; i++) {
powers[i] = power;
unsigned int v = s[i] - 'a' + 1;
hash += v * powers[i];
hashes[i] = hash;
power *= base;
}

hash = 0;
for (int i = n - 1; i >= 0; i--) {
unsigned int v = s[i] - 'a' + 1;
hash += v * powers[n - i - 1];
reverse_hashes[i] = hash;
}

for (int k = 0; k <= n - 1; k++) {
unsigned int h1 = hashes[n - k - 1];
unsigned int h2;
if (k > 0) {
h2 = reverse_hashes[0] - reverse_hashes[n - k];
} else {
h2 = reverse_hashes[0];
}
if (h1 * powers[k] == h2) {
string prefix = s.substr(n - k);
reverse(prefix.begin(), prefix.end());
return prefix + s;
}
}
}
};
``````

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