首页 > 代码库 > 改进版KMP模式匹配算法

改进版KMP模式匹配算法

2024-07-07 18:17:52   225人阅读

背景
朴素匹配算法太低效了。冗余过多，已经比较过的，没必要重复；可以从比较结果中推导出来的，也没必要再重复。
 
核心
主串不回溯，变化要匹配的串的下一次比较的位置。
 
实现
两个函数，一个提供next数组，即存储要匹配的串的每一个元素匹配失败后，下一次要比较的位置的数组。另一个实现匹配。
 
java代码
public class KMP {


//获取next数组
private int[] getNext(char[] t_char){

int size = t_char.length;
int next[] = new int [size];
int i = 0;
int j = -1;

next[0] = -1;
System.out.print(0);

while(i < size - 1){

if(j == -1||t_char[i] == t_char[j]){
i++;
j++;
if(t_char[j] == t_char[i]){   //若下一位比较的值与目前的值相同，则直接把next移到下一个next
next[i] = next[j];
}else
next[i] = j;
System.out.print(next[i] + 1);
}else{
j = next[j];                //运用KMP思想回溯      
}
}
return next;
}

//求子串t在主串s中的位置，若没有，返回-1
public int KMP_Index(String s , String t , int pos){

long start = System.currentTimeMillis();
//判断s,t的大小关系
if(t.length() > s.length()){
return -1;
}

int i = pos;
int j = 0;
char[] s_char = s.toCharArray();
char[] t_char = t.toCharArray();
int next[] = getNext(t_char);
int sl = s_char.length;
int tl = t_char.length;

while(i < sl && j < tl){
if(j == -1 || s_char[i] == t_char[j]){
++i;
++j;
}else{
j = next[j];
}
}
System.out.println("\n"+(System.currentTimeMillis() - start));
if(j == tl){
return i-tl+1;
}else
return -1;
}

public int KMP_Index(String s , String t ){
return this.KMP_Index(s, t, 0);
}


}


联系
我们