我最近在使用RK演算法處理字串匹配的時候，發現對于部分**長字串**，存在無法匹配的情況，不知道是不是演算法本身存在漏洞，但是因為自己能力有限，無法得出這個演算法的漏洞在哪里，所以請各位幫幫忙！
下面是我用java實作的RK演算法，輸入兩個字串，輸出匹配字串在原字串的索引位置，沒有匹配輸出-1
已經經過測驗，可以正常使用
public int RK(String haystack,String needle){
int L = haystack.length();
int N = needle.length();
if(L < N){
return -1;
}
long a = 26;
//防止溢位
long module = (long) Math.pow(2,31);
long h = 0;
long ref_h = 0;
for(int i =0;i<N;i++){
h = (a*h + charToInt(haystack.charAt(i))) % module;
ref_h = (a*ref_h + charToInt(needle.charAt(i))) % module;
}
if(h == ref_h){
return 0;
}
long aN = 1;
for(int i =1;i<=N;i++){
aN = (aN*a) % module;
}
for(int start =1;start < L-N+1;start++){
h = (h *a +charToInt(haystack.charAt(start+N-1)) - aN * (charToInt(haystack.charAt(start-1)))) % module;
if(h == ref_h){
return start;
}
}
return -1;
}但是，當我輸入字串`odgoodgoodbestword` 匹配字串是`odgoodgoodbestword`的時候，卻無法得出匹配的結果
public static void main(String[] args) {
Solution s = new Solution();
//輸出-1,理論輸出1
System.out.println(s.RK("odgoodgoodbestword","dgoodgoodbestword"));
//輸出1
System.out.println(s.RK("qdgoodgoodbestword","dgoodgoodbestword"));
}
uj5u.com熱心網友回復：
indexOf了解一下
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/60331.html
標籤：Java相關
下一篇：集合