拉宾卡普

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;

这是重新计算模式的哈希值，首先删除最左边的字符，然后从文本中添加新字符。