@@ -0,0 +1,1088 @@
+package com.algorithms.string;%0A%0Apublic class RabinKarp %7B%0A%09%0A%09private static final long R = 256;%0A%09private static final long Q = 997; //Q %D4%BD %CD%BB%D4%BD%D0%A1,%D6%B5%C8%A1 10%5E20%0A%09private int m;   %09 //pattern length%0A%09private long rm; %09 // R%5E(m - 1) %25 Q  %D2%AA%C8%A5%D6%B5%0A%09private long patHash;// pattern hash value%0A%09%0A%09public static void main(String%5B%5D args) %7B%0A%09%09RabinKarp rk = new RabinKarp(%2222s%22);%0A%09%09int search = rk.search(%22aa22ss%22);%0A%09%09System.out.println(search);%0A%09%7D%0A%09%0A%09%0A%09public RabinKarp(String pat) %7B%0A%09%09m = pat.length();%0A%09%09rm = 1;%0A%09%09for (int i = 1; i %3C= m - 1; i++) %7B%0A%09%09%09rm = (R * rm) %25 Q;%0A%09%09%7D%0A%09%09patHash = hash(pat, m);%0A%09%7D%0A%09%0A%09//Compute hash for m-digit key%0A%09private long hash(String key, int m) %7B%0A%09%09long h = 0;%0A%09%09for (int j = 0; j %3C m; j++)%0A%09%09%09h = (R * h + key.charAt(j)) %25 Q;%0A%09%09return h;%0A%09%7D%0A%09%0A%09private int search(String txt) %7B%0A%09%09int n = txt.length();%0A%09%09long txtHash = hash(txt, m);%0A%09%09if (patHash == txtHash) return 0;%0A%09%09for (int i = m; i %3C n; i++) %7B%0A%09%09%09txtHash = (txtHash + Q - rm * txt.charAt(i - m) %25 Q) %25 Q;%0A%09%09%09txtHash = (txtHash * R + txt.charAt(i)) %25 Q;%0A%09%09%09if (patHash == txtHash) return i - m + 1;%0A%09%09%7D%0A%09%09return n;%0A%09%7D%0A%09%0A%7D%0A

add rabinKarp string search