-
Notifications
You must be signed in to change notification settings - Fork 0
/
RabinKarp.java
63 lines (51 loc) · 1.47 KB
/
RabinKarp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package algorithms.search.string;
/**
* 在 BF 算法的基础上加上 哈希算法,减少 字符串字符依次对比时间
*
* @author otfot
* @date 2021/04/29
*/
public class RabinKarp {
public boolean match(String master, String pattern) {
int mLen = master.length();
int pLen = pattern.length();
if (mLen < pLen) {
return false;
}
int pHash = hash(pattern);
int count = 0;
for (int i = 0; i < mLen - pLen + 1; i++) {
String substring = master.substring(i, i + pLen);
int mHash = hash(substring);
if (mHash == pHash) {
if (subMatch(substring, pattern)) {
System.out.println("Count:" + count);
return true;
}
} else {
count++;
}
}
System.out.println("Count:" + count);
return false;
}
private boolean subMatch(String str1, String str2) {
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
return false;
}
}
return true;
}
private int hash(String str) {
int count = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) % 2 == 0) {
count += str.charAt(i) * 2;
} else {
count += str.charAt(i);
}
}
return count;
}
}