Rabin Karp (hashing) String pattern matching

Important algorithms (3 Part Series)

1 Kadane’s Algorithm
2 Knuth Morris Prat algorithm[Pattern Matching]
3 Rabin Karp (hashing) String pattern matching

Problem

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

Enter fullscreen mode Exit fullscreen mode

Important algorithms (3 Part Series)

1 Kadane’s Algorithm
2 Knuth Morris Prat algorithm[Pattern Matching]
3 Rabin Karp (hashing) String pattern matching

原文链接：Rabin Karp (hashing) String pattern matching