KMP字串匹配-入门

1、串的定义

这里所说的串指的是字串，就是字符串，当然不是烧烤串。计算机的字串是用编码形式保存的，通常的ASCII码，Unicode编码，中文的GBK等等。对于一个字串，定义为s="a1a2a3....an"，相应的对于另一个字串t=b1b2b2b3....bm，当且仅当n=m，且a1=b1,a2=b2,a3=b3....,an=bm，则两串相等。同时，当满足如下条件时s<t：

n< m ，且a1=b1(i=1,2,3....n)；
有k<=min(m,n)，使ai=bi(i=1,2,3,4,5...k-1)，ak<bk;(这种情况会根据编码计算，可能不同语言有不同处理)

2、朴素的模式匹配算法

模式匹配最先能想到的就是在一片文章中找到指定的单词，如文本的检索，引申到单词的统计。我们最简单想到的就是将材料文本当做一个很长的串，然后用对应的单词去匹配，具体是按照单词的字符一个个匹配，如果匹配到，继续，直到单词尾部，这是最理想的情况，否则，单词首字符再去比较文本第二个字符，依次直到获得结果。归纳如下：

匹配到，检索词，文本串同时推进；
未匹配到，检索词再去执行1，从文本串上次匹配的下一个字符开始；
朴素模式匹配算法的时间复杂度为最好为 $O(m+n)$ ，最差是 $O((n-m+1)*m)$
代码如下
c++

//不存在匹配，返回0，长度存在t[0],s[0]
//s 待匹配，t匹配字串
//t 不空
int index(String s, String t, int pos){
int i = pos;
int j = 1;
while( i <= s[0] && j <= t[0]){
      if(s[i] == t[j]){
            ++i;
            ++j;  
      }else{
        i = i - j + 2;  //从下一个位置开始
        j = 1;  //回到首位比较
      }
  }
   if( j > t[0]){
      return i - t[0];
    }else{
      return 0;
    }
}

java

public class StringPattern {
    public static void main(String[] args) {
        String s = "dsfandkfnadsognoadsngasfsdbvonasdobvnadsodfnasonfo3n2n";
        String p = "";
        System.out.println(index(s, p));
    }

    private static int index(String s, String p) {
        if (s == null || p == null || "".equals(p)) {
            return -1;
        }
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if (j >= p.length()) {
            return i - j;
        }

        return -1;
    }
}

3、KMP模式匹配

KMP算法是D.E.Knuth、J.H.Morris以及V.R.Pratt的发明，可以避免重复遍历的算法，大大提高匹配效率。KMP有些难以理解，这种算法是典型的通过对客观规律的总结，来归纳出一个合理的算法，再通过编程实现和优化的结果。我们看到的只有分析过程和算法结果，并对这个结果加以运用。我尽量简洁的来表述这个算法，会对一些难点进行重点强调和解释。本文是KMP的初级介绍，后面会专门介绍KMP的优化方案。

3.1 KMP原理

首先看下朴素匹配可以优化的点。例如：在S=abcdefgab中匹配T=abcdex，朴素算法首先从a一直匹配到f-x,第6位。然后下次匹配再从T-a去匹配S-b，一直到T-a匹配S-c，一直到再匹配到S-f,T-a。重点：这里我们能够发现，字串T中，首字母a与他之后的字符都不相等，因此之后关于T-a和S中随后字符的比较没有必要进行，这是因为在第一次比较就知道S中往后的都是不等的。推理如下：
$T(a-e)匹配到S(a-e),由于T(a-x)不等，即T(a-e)到S(a-e)不等直接跳到T(a)匹配S(f)$
图示

KMP匹配1

由于我们得到这种经验，如果匹配的串T和目标串S有连续相同的元素，则跳过比较，且这种情况会导致T中j值的变化。所以对于另一种情况如S=abcabaabca,T=abcabx，由于T=(ab)c(ab)x，这里第一次j=1，后面j直接为3，即比较到c的位置，j的取值表示了当期字符之前的串在串中的相似度，相似度越高，j越大。我们将T各个位置上j值的变化表示为一个next的数组保存，抽象成函数表示为：

next[j] = \begin{equation} \begin{cases} 0，j=1\\ \max\{k|1<k<j\}，且p_1...p_{k-1}=p_{j-k+1}...p_{j-1}，表示有相同字串，存在p1=p4，值为k集合最大值\\ 1 , 其他情况 \end{cases} \end{equation}

3.2 next数组推理和使用

T=abcdex
j=1，next[1]=0；j=2，子串为a，其他情况next[2]=1；当j=3，子串ab，a!=b，按公式为其他情况，next[3]=1，最终的结果next[j]=011111
T=abcabx
j=1，next[1]=0；j=2，next[2]=1，其他情况；j=3，子串ab，a!=b，其他情况,next[3]=1；j=4，子串bc，b!=c，其他情况,next[4]=1；j=5，子串abca，a和租后一个a相同，且有p1pk-1=p5-k+1p5-1，有p1=p4，因此k=2，next[5]=3;当j=6，子串(ab)c(ab)，有首ab=尾ab，p1p2=p4p5即p1pk-1=p6-k+1p5，得到next[6]=3
因此得到 $n个相等k值就是n+1$ ，注意一个例子中k值取最终最大的值。

KMP的时间复杂度为 $O(m+n)$ ，和朴素模式匹配最好的情况一致。

3.3 算法实现

c++

//获取匹配串next数组
void get_next(String t, int *index){
  int i,j;
  i=1;
  j=0;
  next[1]=0;
  while( i < t[0]) {
     if( j==0 || t[i] == t[j]){
         ++i;
         ++j;
         next[i] = j;
     }else{
       j = next[j];//没有相同，j保持前值
    }    
  }

}


int index_kmp(String s ,String t, int pos){
    int i = pos;
    int j = 1;
    int next[255];
    get_index(t,next);
     while(i<s[0] && j<= t[0]){
        if(j == 0 || s[i] == t[j]){
            ++i;
            ++j;
        }else{
            j = next[j]
        }
    }
    if( j > t [0]){
       return i - t[0];
    return 0;
}

可以看到和朴素算法差别不大，主要在于next数组的区别
java

public class StringPattern {
    public static void main(String[] args) {
        String s = "abcdexfgab";
        String p = "exf";

        System.out.println(index(s, p));
        System.out.println(indexKmp(s,p));
    }

    private static int index(String s, String p) {
        if (s == null || p == null || "".equals(p)) {
            return -1;
        }
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if (j >= p.length()) {
            return i - j;
        }

        return -1;
    }


    private static int indexKmp(String s, String p) {
        if (s == null || p == null || "".equals(p)) {
            return -1;
        }
        int i = 0, j = 0;
        int[] next = nextArray(p);
        while (i < s.length() && j < p.length()) {
            if (j == -1 || s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j >= p.length()) {
            return i - j;
        }

        return -1;
    }

    private static int[] nextArray(String p) {
        int[] next = new int[p.length()];
        int j = 1;
        int k = -1;
        next[0] = -1;
        while (j < p.length() - 1) {
            if (k == -1 || p.charAt(j) == p.charAt(k)) {
                ++j;
                ++k;
                next[j] = k;
            }else {
                k = next[k];
            }
        }
        return next;
    }
}

保护视力

KMP字串匹配-入门