Longest Happy Prefix Solutions in C++

/// Source : https://leetcode.com/problems/longest-happy-prefix/
/// Author : liuyubobobo
/// Time   : 2020-03-21

#include <iostream>
#include <vector>

using namespace std;


/// KMP-based method
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    string longestPrefix(string s) {

        int n = s.size();
        vector<int> lps(n, 0);

        int len = 0;
        for(int i = 1; i < n; i ++){
            while(len && s[i] != s[len])
                len = lps[len - 1];

            if(s[i] == s[len])
                lps[i] = ++ len;
        }

        return s.substr(0, lps.back());
    }
};


int main() {

    cout << Solution().longestPrefix("level") << endl;
    // l

    cout << Solution().longestPrefix("ababab") << endl;
    // abab

    cout << Solution().longestPrefix("leetcodeleet") << endl;
    // leet

    cout << Solution().longestPrefix("a") << endl;
    // empty

    return 0;
}

/// Source : https://leetcode.com/problems/longest-happy-prefix/
/// Author : liuyubobobo
/// Time   : 2020-03-29

#include <iostream>
#include <vector>

using namespace std;


/// Rolling Hash
/// Not very convincing that it's 100% correct
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    long long MOD = 1e9 + 7;

public:
    string longestPrefix(string s) {

        int n = s.size();
        long long pre_hash = 0, post_hash = 0, pow26 = 1ll;
        int reslen = 0;
        for(int i = 0; i + 1 < n; i ++){
            pre_hash = (pre_hash * 26 + (s[i] - 'a')) % MOD;
            post_hash = ((s[n - i - 1] - 'a') * pow26 + post_hash) % MOD;
            pow26 = pow26 * 26ll % MOD;
            if(pre_hash == post_hash /*&& s.substr(0, i + 1) == s.substr(n - i - 1)*/)
                reslen = i + 1;
        }
        return s.substr(0, reslen);
    }
};


int main() {

    cout << Solution().longestPrefix("level") << endl;
    // l

    cout << Solution().longestPrefix("ababab") << endl;
    // abab

    cout << Solution().longestPrefix("leetcodeleet") << endl;
    // leet

    cout << Solution().longestPrefix("a") << endl;
    // empty

    return 0;
}