1392. 最长快乐前缀(Rabin-Karp 字符串编码\KMP)

暴力解法
python

class Solution:def longestPrefix(self, s: str) -> str:res=6for i in range(len(s)):if(s[:i]==s[len(s)-i:]):res=max(res,i)ans=s[:i]return ans

c++

class Solution {
    
public:string longestPrefix(string s) {
    int n=s.size();string res;for(i=1;i<n;i++){
       if(s.substr(0,i)==s.substr(n-i,i))res=s.substr(0,i);}return res;}
};

class Solution {
    
public:
long long base =41;
long long P=1000000009;
// long long getHash(string s){
    
// long long hashValue=0;
// for(int i=s.size();i>=0;i--){
    
// hashValue=hashValue*base+s[i]-'a'+1;
// hashValue%=P;
// }
// return hashValue;
// }string longestPrefix(string s) {
    int n=s.size();int prefix=0;int suffix=0;int happy=0;long long  mul=1;for(int i=1;i<n;i++){
       prefix=(prefix*base+s[i-1]-'a')%P;suffix=(suffix+(s[n-i]-'a')*mul)%P;if(prefix==suffix){
    happy=i;}mul=mul*base% P;}return   s.substr(0,happy);;}
};