前言

 众所周知,串与序列的算法是计算机科学领域的经典研究课题,尤其是在告诉互联网、大数据与云计算及人工智能已经上升为国家战略性新兴产业的新时代，它的发展与应用更显示出勃勃生机。在生物信息学、信息检索、语言翻译、数据压缩、网络入侵检测、序列模式挖掘等诸多具有挑战性的前沿科学领域中，串与序列的算法都扮演着关键的角色。应用高效的串与序列的算法将是推进和提高这类先进系统总体性能的重要手段。
 在大学这三年我学习了许多关于字符串的算法，下面我将以读书笔记的形式复习并归纳总结一些自己的心得体会。

正文

KMP——我学习的第一个字符串算法

 我第一个学习的字符串算法是KMP算法，他由Knuth、Pratt和Morris提出，并因此而命名。按照我的理解，KMP算法是一种字符串匹配的算法。什么是字符串匹配算法呢？比如说，给定一个主串 s = "ababababb", 模式串 t = "abb"，我们想要找到 t 在 s 中出现的位置/次数, 我们需要从头到尾进行匹配，判断是否在 s 中连续的出现 t 中的每一个字符。

朴素的匹配算法

 在提到KMP算法之前,我们通常都会先讨论朴素的做法,对于每次匹配,我们都进行从头到尾的逐个字符匹配,若遇见失配的情况,就从头开始,这种朴素的匹配算法的时间复杂度是的,其中 n 为主串长度， m 为模式串长度。

int findz(string s, int n, string t, int m){ // 主串为 s, 长度为 n, 模式串为 t, 长度为 m  
  for(int i = 0; i < n - m + 1; i++){
    int j = 0;
    int pos = i;
    while(j < m && s[pos] == t[j]){
      pos++, j++;
    }
    if(j == m){
      return i; // 返回第一个字符在主串的位置
    }
  }
  return -1; // 不存在则返回 -1
}

 我们来分析一下这个算法,它的缺点是每一次失配都需要从头开始匹配,我们观察到当 s 中前后缀有相同情况时,并不需要从头开始匹配,那么能不能设计这么一种算法,使得它每次都能根据前后缀的特点进行快速匹配优化呢？
 这就是KMP算法解决的问题。

KMP算法

 KMP算法它通过引入了一个 next 数组, next 数组是KMP算法的精髓所在, 其中 next[i] 代表第 i 个字符之前的前缀后缀最长公共元素长度。因此,我们第一个需要处理的问题就是如何求出 next 数组

void get_nextz(int nextz[], string t, int m){
  int i, j;
  i = 0, j = nextz[0] = -1;
  while(j < m){
    while(j != -1 && t[j] != t[i]){
      j = nextz[j];  
    }
    nextz[++i] = ++j;
  }
}

 相应的,我们用KMP算法去完成这个匹配问题

int kmp_count(string s, int n, string t, int m){
  get_nextz(nextz, t, m); // 得到next数组
  int i = 0, j = 0;
  while(i < n){
    cout << i << ' ' << j << "\n";
    while(j != -1 && s[i] != t[j]) j = nextz[j];
    i++, j++;
    if(j >= m){
      return i - m; // 返回第一次出现的位置
    }
  }
  return -1; // 不存在
}

KMP算法的时间复杂度分析[^1]

 我们来分析下算法的时间复杂度[^1],在改进的KMP算法中,外层的for循环里i是递增的,一共会执行n次,我们来考虑内层的while循环:

  • j > -1 && s[i] != t[j]   j = nextz[j] 模式串 t 向前滑动j - nextz[j]个单位
  • j == -1 && s[i] != t[j]  主串 s 向前滑动1个单位
  • s[i] == t[j]       i++, j++, 主串 s 和模式串 t 同时向前滑动1个单位

 我们发现上述的情况中, s 和 t 永远是处于往前的状态, 因此最坏的情况是 s 和 t 都到达上界, 分别移动 n 和 m 次,所以得到KMP算法的时间复杂度是

[^1]:本复杂度分析参考了算法设计与分析 第五版 王晓东著