Rabin Karp (ハッシュ) 文字列パターン マッチング

問題

TC:O(n) および 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;
    }
}

以上がRabin Karp (ハッシュ) 文字列パターン マッチングの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。