- it技术
- Java kmp算法记录
public class kmpTest {
public static void main(String
[] args
) {
String s1
= "StrStqString";
String s2
= "String";
int i
= IndexOfKmp(s1
, s2
);
System
.out
.println(i
);
}
private static int index(String s1
, String s2
){
char [] chars1
= s1
.toCharArray();
char [] chars2
= s2
.toCharArray();
int i
= 0 , j
= 0;
while(i
< s1
.length() && j
< s2
.length()){
if(chars1
[i
] == chars2
[j
]){
++i
;
++j
;
}else{
i
= i
- j
+ 2;
j
= 0;
}
}
if(j
>= s2
.length()){
return i
- s2
.length();
}
return -1;
}
private static int IndexOfKmp(String s1
, String s2
){
char [] chars1
= s1
.toCharArray();
char [] chars2
= s2
.toCharArray();
int [] next
= getNext(s2
);
int i
= 0 , j
= 0;
while( i
< s1
.length() && j
< s2
.length()){
if(j
== -1 || chars1
[i
] == chars2
[j
]){
++i
;
++j
;
}else{
j
= next
[j
];
}
}
if(j
>= s2
.length()){
return i
- s2
.length();
}
return -1;
}
private static int[] getNext(String s
){
int [] next
= new int[s
.length()];
char [] chars
= s
.toCharArray();
int i
= 0 , j
= -1;
next
[i
] = j
;
while(i
< s
.length() - 1){
if(j
== -1 || chars
[i
] == chars
[j
]){
++i
;
++j
;
next
[i
] = j
;
}else{
j
= next
[j
];
}
}
return next
;
}
private static int[] getNextPro(String s
){
char [] chars
= s
.toCharArray();
int i
= 0 , j
= -1;
int next
[] = new int[s
.length()];
next
[i
] = j
;
while(i
< s
.length() - 1){
if(j
== -1||chars
[i
] == chars
[j
]){
++i
; ++j
;
if(chars
[i
] == chars
[j
]){
next
[i
] = j
;
}else{
next
[i
] = next
[j
];
}
}else{
j
= next
[j
];
}
}
return next
;
}
}
