最长快乐前缀

最长快乐前缀
分别同步计算前后缀字符串hash值进行比较

class Solution {
    public String longestPrefix(String s){
        //字符串hash
        //预处理
        int MOD=1000000007;
        int p=13331;
        int n=s.length();
        long prefix=0;
        long subfix=0;
        int index=0;long mul=1;//权重
        for(int i=1;i<s.length();i++){
            prefix=((long)prefix*p+(s.charAt(i-1)-'a'))%MOD;
            subfix=(subfix+(long)(s.charAt(n-i)-'a')*mul)%MOD;
            if(prefix==subfix){
                index=i;
            }
            mul=(long)mul*p%MOD;
        }
        return s.substring(0,index);
    }
}

字符串hash

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
int p=131;
        Set<Integer> set=new HashSet<>();
        for (String s : dictionary) {
            int h=0;
            for(int i=0;i<s.length();i++){
                h=h*p+s.charAt(i)-'a'+1;
            }
            set.add(h);
        }
        String[] s = sentence.split(" ");

        String res="";
        for (String s1 : s) {
            //对于每一个前缀
            String prefix="";
            int h=0;
            for(int i=0;i<s1.length();i++){
                prefix+=s1.charAt(i);
                h=h*p+s1.charAt(i)-'a'+1;
                if(set.contains(h)){
                    break;
                }
            }
            res+=prefix+' ';
        }

        return res.trim();
    }
}