1392. 最长快乐前缀

链接：

1392. 最长快乐前缀

题解：

class Solution {
public:string longestPrefix(string s) {if (s.size() <= 0) {return "";}int MOD = 1e9 + 7;// 构建26的n次方，预处理std::vector<long> pow26(s.size());pow26[0] = 1;for (int i = 1; i < pow26.size(); ++i) {pow26[i] = (pow26[i-1] * 26)%MOD;}// 构建前向hashstd::vector<long> prefix_hash(s.size());prefix_hash[0] = s[0] - 'a';for (int i = 1; i < prefix_hash.size(); ++i) {prefix_hash[i] = (prefix_hash[i-1] * 26 + (s[i]- 'a')) % MOD;}// 构建后面的hashstd::vector<int> post_hash(s.size());post_hash[s.size()-1] = s[s.size()-1] - 'a';for (int i = s.size()-2; i >= 0; --i) {post_hash[i] = ((s[i] - 'a') * pow26[s.size()-i-1] + post_hash[i+1])%MOD;}for (int len = s.size()-1; len >= 1; --len) {// 判断字符串是否相等if (prefix_hash[len-1] == post_hash[s.size()-len] &&equal(s, 0, len-1 , s.size() - len, s.size()-1)) {return s.substr(0, len);}}return "";}
private:bool equal(const std::string& a, int l1, int r1, int l2, int r2) {for (; l1 <= r1 && l2 <= r2; ++l1, ++l2) {if (a[l1] != a[l2]) {return false;}}return true;}
};