KMP字串匹配-入门

1、串的定义

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

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

2、朴素的模式匹配算法

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

1. 匹配到，检索词，文本串同时推进；
2. 未匹配到，检索词再去执行1，从文本串上次匹配的下一个字符开始；
   朴素模式匹配算法的时间复杂度为最好为，最差是
   代码如下
   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中往后的都是不等的。推理如下：

图示

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的数组保存，抽象成函数表示为：
保护视力