Find shortest palindrome which can be obtained by mutating input string by adding elements to the front

Solution for https://leetcode.com/problems/shortest-palindrome/submissions/

everyone is writing KMP and Manacher, I would just write a simple hashing algorithm:

    const int p = 31;
    const int M = 1e9 + 7; // I prefer always use mod prime even if we don't need to 
	// find a reverse element. Just for consistancy, it is faster to write one standard way
	// every time instead of creating something ad hoc
    string shortestPalindrome(string s) {
        const int n = s.size();
        if (s.size() == 0) return "";
        // compute the length of longest prefix palindrome
        long long fhash = 0, bhash = 0;
        int lenMaxPrefixPalindrome = 0;
        long long pp = 1;
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a' + 1;
            fhash = (fhash + (c*pp)%M)%M;
            pp = (p * pp)%M;
            
            bhash = (bhash * p)%M + c;
            
            if (fhash == bhash) {
                lenMaxPrefixPalindrome = i;
            }
        }
        lenMaxPrefixPalindrome += 1;
        // now just copy the not palindromic suffix in reversed order
		// to the buffer and than copy original string there
        string res(2*n - lenMaxPrefixPalindrome, 'a');
        int j = s.size() - 1;
        for (int i = 0; i < 2*n - lenMaxPrefixPalindrome; ++i) {
            if (i < n - lenMaxPrefixPalindrome) {
                res[i] = s[j];
                --j;
            } else {
                res[i] = s[i - (n - lenMaxPrefixPalindrome)];
            }
        }
        
        return res;
    }

Solution using KMP

    string shortestPalindrome(string s) {
        if (s.size() == 0) return s;
        int n = s.size();
        
        string rev = s;
        reverse(rev.begin(), rev.end());
        vector<int> pif = prefix_function(s + "#" + rev);
        
        return rev.substr(0, n - pif.back()) + s;
    }

TODO: For the sake of studying, lets learn:

KirillLykov/find-shortest-palindrome.md