0%

数据结构系列之串(Java)

串的朴素模式匹配

较简单,略过。

KMP算法(朴素模式匹配的优化)

朴素模式匹配的缺点是:每当模式串匹配失败的时候,当前的匹配指针都只是往后移动一位,也就是只是把模式串右移一位,而且主串的扫描指针(模式串中匹配到哪一位)都要经常回溯,会造成多余的开销。

假定在某个主串中要匹配google这个模式串,那么其匹配逻辑如下:

  • 声明主串扫描指针为i;
  • 声明模式串扫描指针为j;
  • KMP的算法关键在于匹配失败时,j回溯,而i不回溯(下标从0开始)。
  • 当j>0匹配成功时,j++,i++
  • 当j=0匹配不成功时,j不变,i++
  • 当j>0匹配不成功时,j回到最后一个有可能接下来匹配成功的下标,i不变(比如模式串google,在j等于4时不匹配,那么j应该回溯到1)

j指针的具体回溯如下,并且可以一个int类型数组来存储器其回溯的下标。

  • 若当前两个字符匹配,则i++,j++
  • 若j=0时发生不匹配,则应让i++,但是此时的next[j]=-1
  • 若j=1时发生不匹配,则应让j回到0
  • 若j=2时发生不匹配,则应让j回到0
  • 若j=3时发生不匹配,则应让j回到0
  • 若j=4时发生不匹配,则应让j回到1
  • 若j=5时发生不匹配,则应让j回到0

数组next[0]=-1 next[1]=0 next[2]=0 next[3]=0 next[4]=1 next[5]=0

BOILERPLATE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int[] next;
public int kmp(String main, String pattern){
// 先构建模式串的next数组,下标从0开始
initNext(pattern);
int i=0,j=0;
while(i < main.length() && j < pattern.length()){
if(j == -1 || main.charAt(i) == pattern.charAt(j)){
++i;
++j;
}else{
j = next[j];
}
}

if(j >= pattern.length()){
return i - pattern.length();
}else{
return -1;
}
}

next数组的构建(fail数组)

  • 串的前缀:包含第一个字符,且不包含最后一个字符的子串。
  • 串的后缀:包含最后一一个字符,且不包含第一一个字符的子串。

对于长度只有1的串来说,其前后缀都是空集。
当第j个字符匹配失败时,假定前面1~j-1个字符组成的串为S,那么,next[j]=S的最长相等前后缀的长度(当下标从1开始时,需要+1)。

BOILERPLATE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void initNext(String pattern){
// 冗余出最后一个元素位,防止下标溢出
next = new int[pattern.length() + 1];
int i = 1, j = 0;
next[0] = j;
while(i < pattern.length()){
if(j == -1 || pattern.charAt(i) == pattern.charAt(j)){
++i;
++j;
next[i] = j;
}else{
j = next[j];
}
}
}

google为例,上面的Boilerplate执行过程如下:

  • j==-1 i=1 j=0 next[1]=0
  • o!=g i=1 j=0 j = next[0] = -1
  • j==-1 i=2 j=0 next[2]=0
  • o!=g i=2 j=0 j = next[0] = -1
  • j==-1 i=3 j=0 next[3] = 0
  • g==g i=4 j=1 next[4] = 1
  • l!=o i=4 j=1 j=next[1] = 0
  • l!=g i=4 j=0 j=next[0] = -1
  • j==-1 i=5 j=0 next[5] = 0
  • e!=g i=6 j=1 break;

KMP算法的优化