# My fingerprint based solution in c++ (4ms)

• The idea is to compute the fingerprints of the first k characters of the string, and fingerprints of the first k characters reversed. Then find the largest k where the fingerprint and reversed fingerprint of the first k characters are the same. Of course you verify s.substr(0, k) is a palindrome (it's likely to be) and continue finding if it's not.

The key is that fingerprints can be computed in O(n) time.

``````class Solution {
public:
static const int BASE = 19;
string shortestPalindrome(string s) {
int n = s.size();
if (n == 0) {
return "";
}
int fp[n];
int fp_r[n];
fp_r[0] = fp[0] = static_cast<int>(s[0]);
int mul = BASE;
for (int i = 1; i < n; ++i) {
// it's ok to overflow.
int tmp = static_cast<int>(s[i]);
fp[i] = fp[i - 1] * BASE + tmp;
fp_r[i] = fp_r[i - 1] + tmp * mul;
mul *= BASE;
}
int i = n - 1;
while (i) {
if (fp[i] == fp_r[i] && verify(s, i)) {
break;
}
i--;
}
return string(s.rbegin(), s.rend()) + s.substr(i + 1, n - i - 1);
}
bool verify(const string& s, int idx) {
for (int i = 0, j = idx; i < j; ++i, --j) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
};``````

• Very neat solution. Thanks for sharing.

But the base value selection is kind of mysterious for me.

I tried your code with 2 as base value, it got TLE for the very long all "a....a" case.

Then I tried 3, it passed but used 8ms instead.

I can imagine the base value, may have impact in some cases, as a small value like 2 may cause a lot false positive match and would cause more verify to be triggered.

But, I really don't see why the base value would have impact on the all "a....a" case.

Any thoughts on this, and why did you choose 19?

• I didn't quite remember the reason, but at least the BASE and 256 should be relatively prime, and that's why 3 performs much better than 2.

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