1392. 最长快乐前缀

本文主要是介绍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;}
};

这篇关于1392. 最长快乐前缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---