Rabin Karp (hachage) Correspondance de modèle de chaîne

Problème

TC:O(n) et SC:O(n)

// using rabin karp hashing approach

class Solution {
    public String shortestPalindrome(String s) {
        int prefix = 0;
        int suffix = 0;
        int lastIndex =-1;
        int base = 29;
        int power = 1;
        int mod = (int)(1e9 + 7);
        String str = "";
        for(int i =0;i<s.length();i++){
            int ch = (s.charAt(i)-'a') +1;

            prefix = (int)((1L * prefix * base) % mod);
            prefix = (int)((prefix + ch) % mod);

            suffix = (int)((suffix + 1L * ch * power) % mod);
            power = (int)((1L * power * base) % mod);
            if(prefix == suffix){
                lastIndex =i;
            }
        }
        str = s.substring(lastIndex+1);
        return new StringBuilder(str).reverse().toString()+s;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!