KMP模式匹配算法-串的应用

前言

好久不见~各位看客老爷们，距离上次小向上班已经过去了好久--TT，小向也不想，但是被一个地方卡住了好久，最近才弄清楚。那么废话不多说，让我们进入今天的主题叭~数据结构之串及其应用KMP模式匹配算法。

还记得前段时间，小编参加英语考试，面对大量的生词，小编人都吓傻了，可是全部记忆一遍肯定来不及，记忆出现频率最高的肯定是效率最快的，这件事情说起来很简单，但是怎么才能知道什么单词出现的频率最高呢？这里面涉及到许许多多的东西，今天我们就不全部展开讲解，不过，这里面最重要的其实就是去找一个单词在一篇文章中的定位问题。即串的模式匹配。

什么是串？

下面让我们来了解一下串。

虽然看到串的第一眼，大家可能有一点蒙的感觉，串？羊肉串？或者是别的balabala的东西。其实这里的串，指的是字符串。串：由零个或者多个字符组成的有限序列，又名叫字符串。一般我们把串记为s=”a1a2a3……an”,其中s是串的名称，用双引号或者单引号括起来的内容就是串的值，注意，在这个位置，双引号不是串的内容。打个比方说，《静夜思》“床前明月光，疑是地上霜。举头望明月，低头思故乡”，那么此时，《静夜思》就是串的名称，“床前明月光……”才是内容。 零个字符是什么意思呢？就是啥也没有，这样的串，我们又称为空串，""直接这样表示就可以了。他的长度为0.在串的定义中我们可以发现，串是有顺序的，相邻的字符之间有前驱和后继的关系。并且串是有限的，一定要注意，串是有限的！

下面再让我们认识一个概念，主串，子串以及空格串。主串子串，其实很好理解，整个串的所有内容就是主串，而串中任意个数的连续字符组成的子序列称为该串的子串。那空格串就更好理解了，就是只包含有限个空格的串，记住是有限个空格，可以不是一个，但是不可能是无限个。现在再来看《静夜思》，我们就知道了，整首古诗就是一个主串，而里面的每个句子或者每连续的几个字，就是它的子串。

 大致清楚了串的一些定义之后，我们来了解一下串的比较大小方式。对于两个数来说，比较大小非常容易，2>1……。但是串怎么比较大小呢？其实串的比较大小方式大家猜应该也都可以猜出来，就是判断他们挨个字母的前后顺序。打一个比方来说，smart，stupid，他们的第一个字母都是s，认为不存在大小差异，而第二个字母，”m”字母在”t”字母之前，所以”m”<”t”.

但是事实上，对于计算机来说，他是不知道哪个字母在前哪个字母在后的，他是通过组成串的字符之间的编码来进行的。现代计算机一般都是通过ASCII编码，但是由于ASCII码是用7位二进制表示一个字符，总共只能表示128个字符，所以扩展ASCII码由8位二进制数表示一个字符，这样就可以表示256个字符，满足了大部分国家的需要。可是，对于我们国家那可是远远不够的，我们国家除了汉语，还有土家语，蒙古语……等等语言，所以就有了现在的Unicode编码，一般用16位的二进制数表示一个字符。

  那么现在我们就来正式的总结一下串的比较。

对于两个长度相等的串来说，必须每个相应位置的字符都相等，才算是相等。即a1=b1,a2=b2,……，an=bn.

 对于两个长度不相等的串来说，s1=”a1a2……an”,s2=”b1b2……bm”,

 如果n<m，且满足ai=bi，则更长的串更大。比如说，s1=“brain”,s2=”brainstorm”,就有s1<s2.

 对于n<m，但存在某个i，使得a1=a2……ai-1=bi-1，但是ai>bi，则s1>s2.

 大致的了解了串以后，本来是应该继续介绍串的抽象数据类型和储存结构，但是串的抽象数据类型和储存结构和栈类似，这里就不多加叙述了。下面就让我们进入串的应用部分，模式匹配算法。

朴素匹配算法

在刚开始的时候，我觉得写一个查找单词的程序很简单，就依次来比较就行了。过程在这里给大家进行简单的介绍。

 对于一个主串s=“annyainy”，我们需要查找子串t=””yibeizi”.我最开始的思路是依次进行匹配。

 主串s从第一位开始，s和t第一个字母不匹配，那么将s2和t1进行比较，依次类推，直到最后匹配成功。简单的说，就是对主串的每一个字符作为子串开头，与待匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。

 下面给出相应的代码

int index（string s, string t,int pos) 
{
  int i = pos;
  / pos是指开始搜索的位置，即开始搜索时的下标
  int j = 0；/ 这是当前子串的下标
  while(i < s.length() && t < b.length()) / 只有当i小于等于主串长度且j小于等于子串长度时进行循环 
  {
    if（s[i] == t[j]) 
    {
      ++i;
      ++t;
    } else 
    {
      i = i - j + 2 / i退回到上次匹配位置的下一位
      j = 1;
    }
    if(j = b.length())
    return i - b.length(); else
    return 0;
  }

那么现在一个简单的匹配代码我们已经写出来了，但是这是最简单的，也是最慢的。现在让我们来分析一下，如果每一次不成功的匹配都发生在串t的最后一个字符。举一个例子，s为“aaaaaaaaaaaab”，t为“aaaaaaab”，那么需要每次匹配到最后我们才知道，原来不匹配。这样的情况下，时间复杂度就是O（（n-m+1）*m）。

 相信大家看到这样分析下来肯定会说，这确实太麻烦了，甚至难以忍受，那么就让我们来看看一种更高效的算法。由D.E.Knuth，J.H.Morris和V.R.Pratt发表的一个模式匹配算法，简称KMP算法。

KMP模式匹配算法

在最开始，我们先来看一个串，s=abcababcaaccda……，t=abcabz，他们在进行匹配的时候，匹配到第六位时发现不匹配，按照朴素匹配算法，他们会依次往前移动一位，再重新进行比较，即整个匹配过程我们是通过s的i的值的不断回溯来进行，但是，我们知道，t的第一位和s的第一位肯定不匹配，依次类推，直到和s的4位开始比较，才算步入正轨，那么我们可不可以把这些很显然不对的步骤删掉，把那些肯定匹配的步骤跳过呢？对，基于这种观点，大佬们提出了KMP算法来解决这些完全没有必要的回溯。

 如果i的值不回溯，也就是大小不能发生变化，那么要考虑的变化就是j的值了。通过对朴素匹配算法的观察，我们可以发现，要确定j值的变化，其实我们只要将当前j所在的位置和前面进行比较，如果出现了相同的字符，那么j的变化也会不一样，也就是说，j值的变化只取决于自身而不取决于主串。

 再拿上面的例子来说，t=abcdef，当中没有任何重复的字符，那么j就从6变为1，如果t=abcabz，当匹配到z的时候，发现不匹配，此时j就从6变为3，而不是1，因为前缀”ab”和z之前的后缀”ab”是相等的。由此我们就可以知道j的值取决于当前字符之前的串的前后缀的相似度。

如果把t串的各个位置的j值变化定义为一个数组next，那么数组next的长度就是t串的长度，于是我们就可以得到下面的函数定义。

这里我们需要先明确一个概念，前缀和后缀。对于子串acesdz来说，当j=5时，他的去掉第五个字符的子串是“aces”，前缀就是去掉再最后一个字符“s”，依次的子串，即a,ac,ace，那么后缀也很清楚了，去掉最前面一个，即s,es,ces.

 那么next数组是怎么推导的呢？对于子串acesdz

1）当j=1时，next[1]=0.

2）当j=2时，j由1到j-1就只有字符“a”,属于其他情况next[2]=1.

3）当j=3时，j由1到j-1的串就是“ac”，显然“a”和”c”不等，属于其他情况，next[3]=1.

4）以此类推，最终next[j]为011111.

对于子串aecaex

1）当j=1时，next[1]=0.

2）当j=2时，next[2]=1.

3）当j=3时，next[3]=1.

4）当j=4时，next[4]=1.

5）当j=5时，next[5]=2.

void get_next(string t, int* next) 
{
  int i = 1;
  int j = 0;
  next[1] = 0;
  while(i < t[0]) 
  /*在这个位置t[0]表示t的长度*/ 
  {
    if(j == 0 || t[i] == t[j]) 
    {
      ++i;
      ++j;
      next[i] = j;
    } 
    else
      j = next[j];
  }
}

6）当j=6时，next[6]=3.

    我们根据经验就可以知道，如果前后缀一个字符相等，那么next[j]=1+1，n个字符相等就是next[j]=1+n.

    下面我们给出next数值推导的代码，

   下面给出具体的匹配过程的代码

/*此处s为主串，t为子串，pos为刚开始匹配的位置*/
int kmp(string s, string t, int pos) 
{
  int i = pos;
  int j = 1;
  int next[255];
  get_next(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]; 
  else
    return 0;
}

    KMP算法的时间复杂度是O(n+m），相比较朴素匹配算法来说是快了很多，但是这种优势只体现在重复部分很多的情况，否则差异不明显。下面让我们来看看KMP算法的进一步优化。

KMP的改良

如果主串为s=aaaacde,子串为t=aaaaaz，next[j]=012345，i=5,j=5时，发现不匹配，此时j变为4，仍然不匹配，然后变成3，依然不匹配，后面肯定也是一样的不匹配，因为都是a，那么其实这些匹配都是不必要的，可以省去。那么我们完全可以用第一位的a的next数值来代替后面a的next数值，因此我们对next进行了改良。

void get_naxtval(string t, int* nextval) 
{
  int i = 1;
  int j = 0;
  nextval[1] = 0;
  while (i < t[0]) 
  {
    if (j == 0 || t[i] == t[j]) 
    {
      ++i;
      ++j;
      if (t[i] != t[j])
      nextval[i] = j; else
      nextval[i] = nextval[j];
    }
  }
}

 匹配算法和之前的是一样的这里就不再重复。这里nextval的推导就也不重复了，和next的推导过程大致相同。

KMP的再改良

   虽然介绍完了KMP算法的标准形式，但是，我发现在实际的操作中，有一些方面并不是很好操作，比如t[0],s[0]为字符串的长度，这里就需要进行一些别的操作实现，s[0],t[0]为字符串长度，麻烦了。在最后给出我在后面改进的KMP改良算法。希望大家在前面的内容看明白以后，来看看这个改良版本的算法。

#include<iostream>
#include<string>
using namespace std;
void get_nextval(string t, int* nextval) 
{
  int i = 1;
  int j = 0;
  int l = t.length();
  nextval[0] = -1;
  nextval[1] = 0;
  while (i <l) 
  {
    if (j==-1||t[i] == t[j]) 
    {
      ++i;
      ++j;
      if (t[i] != t[j])
      nextval[i] = j; else
      nextval[i] = nextval[j];
    } else
    j = nextval[j];
  }
}
int kmp(string s, string t, int pos) 
{
  int l1 = s.length();
  int l2 = t.length();
  int nextval[255];
  get_nextval(t, nextval);
  int i = pos;
  int j = 0;
  while (i < l1&&j<l2) 
  {
    if (j==-1||s[i] == t[j]) 
    {
      i++;
      j++;
    } else
    j = nextval[j];
  }
  if (j ==l2)
  return i - l2; else
  return -1;
}
void main() 
{
  string s, t;
  int pos;
  cout << "请输入主句"<<endl;
  cin >> s;
  cout << "请输入查找句"<<endl;
  cin >> t;
  cout << "请输入从哪一个字符开始查找（第一个字符的位置为0）"<<endl;
  cin >> pos;
  cout << "查找句位于" << kmp(s, t, pos);
}

  快过年了，小编在这里给各位看客老爷们提前说一声，祝大家新年快乐！