Algorithm-and-Data-Structure/AlgorithmCode/BoyerMoore.java at master · lemidia/Algorithm-and-Data-Structure · GitHub

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
publicclassBoyerMoore {

publicstaticvoidboyerMoore (Stringtext, Stringpattern) {
inti = pattern.length()-1;
intj = pattern.length()-1;

while (i <= text.length()-1) {
if (text.charAt(i) == pattern.charAt(j)) {
if (j == 0){
System.out.println("Pattern matched index at " + i);
i += pattern.length();
j = pattern.length()-1;
 }
else {
j--;
i--;
 }
 } else {
i = i + pattern.length() - (lastIdx(text.charAt(i), j-1, pattern)+1);
j = pattern.length()-1;
 }
 }
 }

publicstaticintlastIdx(chara, intj, Stringpattern) {
while (j != -1) {
if (pattern.charAt(j) == a)
returnj;
j--;
 }
return -1;
 }
publicstaticvoidmain(String[] args) {
Stringtext = "aabaaabaabada";
Stringpattern = "aabaa";
boyerMoore(text, pattern);

//Output:
// Pattern matched index at 0
// Pattern matched index at 4
 }
}