I've been using fairly RK algorithm processing on string matching, found that for some * * * *, long string existence of mismatch, don't know whether I loopholes in the algorithm itself, but because of his ability is limited, can't draw the algorithm of the leak, so please help!

Below is I use Java implementation fairly RK algorithm, input two strings, the output matching strings in the original string index position, there is no matching output - 1
Has been tested, can be normal use

 public int fairly RK (String haystack, String needle) {
Int L=haystack. Length (); 
Int N=needle. Length (); 
If (L & lt; N) {
return -1; 
} 

Long a=26; 
//to prevent overflow 
Long module=(long) Math. Pow (2, 31); 


Long h=0; 
Long ref_h=0; 

For (int I=0; IH=(a * h + charToInt (haystack. CharAt (I))) % module; 
Ref_h=(a * ref_h + charToInt (needle. The charAt (I))) % module; 
} 
If (h==ref_h) {
return 0; 
} 

Long aN=1; 
For (int I=1; I<=N; I++) {
The aN=% module (aN * a); 
} 

For (int start=1; Start & lt; L - N + 1; Start++) {

H=(a + h * charToInt (haystack. CharAt (start + N - 1)) - aN * (charToInt (haystack. CharAt (start - 1)))) % module; 

If (h==ref_h) {
Return the start; 
} 
} 
return -1; 
} 

However, when I input string ` odgoodgoodbestword ` matching string is ` odgoodgoodbestword `, cannot match the results

 public static void main (String [] args) {
The Solution s=new Solution (); 
//output - 1, the theory of output 1 
System. The out. Println (s.R K (" odgoodgoodbestword ", "dgoodgoodbestword")); 
//output 1 
System. The out. Println (s.R K (" qdgoodgoodbestword ", "dgoodgoodbestword")); 

} 

CodePudding user response:

IndexOf know about the