拉賓卡普

Rabin-Karp 演算法或 Karp-Rabin 演算法是一種字串搜尋演算法，它使用雜湊來查詢文字中的一組模式字串中的任何一個。它的平均和最佳情況執行時間是空間 O 中的 O（n + m）（ p），但其最壞情況時間是 O(nm)，其中 n 是文字的長度，m 是模式的長度。

java 中用於字串匹配的演算法實現

void RabinfindPattern(String text,String pattern){
    /*
    q a prime number
    p hash value for pattern
    t hash value for text
    d is the number of unique characters in input alphabet
    */
    int d=128;
    int q=100;
    int n=text.length();
    int m=pattern.length();
    int t=0,p=0;
    int h=1;
    int i,j;
//hash value calculating function
    for (i=0;i<m-1;i++)
            h = (h*d)%q;
        for (i=0;i<m;i++){
        p = (d*p + pattern.charAt(i))%q;
        t = (d*t + text.charAt(i))%q;
        }
//search for the pattern 
    for(i=0;i<end-m;i++){
        if(p==t){
//if the hash value matches match them character by character
            for(j=0;j<m;j++)
                if(text.charAt(j+i)!=pattern.charAt(j))
                break;
            if(j==m && i>=start)
                System.out.println("Pattern match found at index "+i);            
        }
        if(i<end-m){
            t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
            if(t<0)
                t=t+q;
        }    
    }                                
}

在計算雜湊值時，我們將它除以素數以避免碰撞。在除以素數之後，碰撞的機率會更小，但是仍然有可能兩個字串的雜湊值相同，所以當我們得到一個匹配，我們必須逐個字元檢查，以確保我們得到一個正確的匹配。

t =（d *（t - text.charAt(i)* h）+ text.charAt（i + m））％q;

這是重新計算模式的雜湊值，首先刪除最左邊的字元，然後從文字中新增新字元。