朴素的模式匹配算法
图1
第1步:主串从第一位开始(i=0),子串也从第一位开始(j=0),一个个比较。前三位比较相等,当i=3,j=3时,匹配失败。
图2
第2步:主串从第二位开始(i=1),子串则从第一位开始(j=0),一个个比较。如果匹配成功,主串和子串同时往后移一位。如果匹配失败,主串往后移一位,继续和子串第一位比较。即:i=i-j+1
图3
第3步:如果在主串中完全匹配子串,返回子串插入第一个字符的位置,即:i-j;否则返回-1。
public static int findIndex (String as, String ps) {
char[] t = as.toCharArray();
char[] p = ps.toCharArray();
int i = 0; //i 主串位置
int j = 0; //j 子串位置
while (i < t.length && j < p.length) {
if (t[i] == p[j]) {
i ++;
j ++;
} else {
i = i -j + 1;
j = 0;
}
}
if (j == p.length) {
return i - j;
}
return -1;
}
public static void main (String[] args) {
String as = "abcdabcabcab";
String ps = "abcab";
System.out.print("Index: " + findIndex(as, ps));
}
输出结果:
Index: 4
KMP模式匹配算法
朴素的模式匹配算法效率比较低,图1一旦匹配失败,主串i指针就要回溯到i=1的位置(从0开始计数),子串的j指针回溯到初始位置j=0,一个个匹配,如图2。
而在实际过程中,主串的第二位(b),第三位(c)比较是多余的。因为为主串匹配失败的位置前面除了第一个a之外再也没有a了。保持i的位置不动,只移动子串的j指针。而j指针的移动位置,就涉及到了KMP算法。
什么是KMP算法?D.E .Knutb 、J.H.Morris 和Y.R. Pra位(其中Knuth 和Pra忧共同研究, Morris 独立研究)发表一个模式匹配算法, 可以大大避免重复遍历的情况,我们把它称之为克努特一莫里斯一普拉特算法, 简称KMP 算法。
KMP算法中,指针j的位置变化和主串没有关系,只跟自身结构中有多少个重复的字符有关。我们把子串各个位置的j值的变化定义为一个数组next 。用数学公式定义如下:
图4
其中k表示:当匹配失败时,j要移动的下一个位置
图5
图5中,子串abcab,当j=0时,定义next[0]=-1;当j=1时,0 ~ j-1,只有一个字符a,属于其他情况,next[1]=0;当j=2,3时,0 ~ j-1没有相同的字符,属于其他情况,next[2]=next[3]=0;当j=4,0 ~ j-1有一个字符a重复,推算next[4]=1。即当有重复字符时,next[++j]=++k。
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1) {
if (k == -1 || p[j] == p[k]) {
++j;
++k;
next[j] = k;
} else {
k = next[k];
}
}
for (int i=0; i<p.length; i++) {
System.out.print(next[i] + ", ");
}
return next;
}
输出:
-1, 0, 0, 0, 1,
有了next数组就知道j回溯的位置,KMP算法代码如下:
public static int findIndex (String as, String ps) {
char[] t = as.toCharArray();
char[] p = ps.toCharArray();
int i = 0; //i 主串位置
int j = 0; //j 子串位置
int[] next = getNext(ps);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) {
i ++;
j ++;
} else {
j = next[j]; //j回溯位置,i保持不变
}
}
if (j == p.length) {
return i - j;
}
return -1;
}
public static void main (String[] args) {
String as = "abcdabcabcab";
String ps = "abcab";
System.out.print("\nIndex: " + findIndex(as, ps));
}
输出结果:
Index: 4
算法改进
KMP算法是有缺陷的,如果我们的主串aaaabcae,子串aaaaax,其next 数组为-1, 0, 1, 2, 3, 4。
当i=4,j=4时,不匹配。根据next数据j指针依次回溯到3,2,1,0。但是我们发现j指针回溯到3,2,1是完全咩有必要的,因为前面的字符a全部相等。我们更希望能够一次性回溯到j=0。即得到图7的nextval数组
图7
public static int[] getNextVal(String ps) {
char[] p = ps.toCharArray();
int[] nextval = new int[p.length];
nextval[0] = -1;
int j = 0;
int k = -1;
while (j < p.length-1) {
if (k == -1 || p[j] == p[k]) {
++j;
++k;
if (p[j] == p[k] && k!=0) { //与getnext函数唯一不同地方,增加if判断
nextval[j] = nextval[k]; //k不在第一位。如果与前缀字符相同,则将前缀字符的nextval值赋值给nextval j的位置
} else {
nextval[j] = k;
}
} else {
k = nextval[k];
}
}
for (int i=0; i<p.length; i++) {
System.out.print(nextval[i] + ", ");
}
return nextval;
}
输出结果:
-1, 0, 0, 0, 0, 4,
网友评论