数据结构系列之串（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:

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:

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算法的优化