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 | package KMP;
public class Main {
public static void main(String[] args) {
System.out.println("KMP");
KMP kmp = new KMP("THIS IS A TEST TEXT", "TEST");
kmp.search();
KMP kmp1 = new KMP("AABAACAADAABAABA", "AABA");
kmp1.search();
}
}
class KMP{
String texts = "";
String pattern = "";
int nt, np;
int[] lps;
KMP(String t, String p){
texts = t;
pattern = p;
nt = texts.length();
np = pattern.length();
lps = new int[np];
}
void preProcess(){
for(int i=1; i<np; ++i){
int l = lps[i-1];
while(l>0 && pattern.charAt(i)!=pattern.charAt(l)){
l = lps[l-1];
}
if(pattern.charAt(l)==pattern.charAt(i)){
lps[i] = l+1;
}
}
}
void search(){
preProcess();
int i = 0, j = 0;
while(i<nt && j<np){
if(texts.charAt(i)!=pattern.charAt(j)){
i++;
j = lps[j];
}else{
if(j==np-1){
System.out.println(i+1-np);
i++;
j = lps[j];
}else{
i++;
j++;
}
}
}
}
}
|
No comments:
Post a Comment