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 중국어 웹사이트의 기타 관련 기사를 참조하세요!