?? kmp.java
字號:
package OTHERS;
import java.util.Scanner;
public class KMP {
static int[] computeNext(String str){
int size = str.length();
int[] next= new int[size];
next[0] = -1;
next[1] = 0;
for(int i=2;i<size;i++){
int j = next[i-1]+1;
while(j>0&&(str.charAt(i-1)!=str.charAt(j-1))){
j=next[j-1]+1;
}
next[i]=j;
}
return next;
}
static int SringMatch(String A,String B){
int start = -1;
int sizeOfA = A.length();
int sizeOfB = B.length();
int[] next = computeNext(B);
int i=0,j=0;
while(start==-1&&i<sizeOfA){
if(B.charAt(j)==A.charAt(i)){
j++;
i++;
}
else{
j = next[j];
if(j==-1){
j=0;
i++;
}
}
if(j==sizeOfB){
start = i-sizeOfB;
}
}
return start;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String A = "xyxxyxyxyxx";
String B = "xyxy";
System.out.println(SringMatch(A,B));
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -