【数据结构与算法分析】0基础带你学数据结构与算法分析05--串 (string)

前言

串是一种特殊的线性结构，它的内部元素只存储字符，因此又称为字符串。其特殊性主要来源于我们对字符序列的依赖程度很高，而特化一个线性结构并为其增加一些针对于字符的常用算法，可以方便我们的使用，提高编码效率。

在大部分的实现中，string 都有一个标志结尾的字符 \0 ，其 ASCII 值为 0，因此在遇到 \0 时就认为这个字符串结束。但是有一些实现使用单独的变量来标记，因此这种字符串中即使存在 \0 也可能并不是串的结尾。因此串的长度为真实的长度减一 (因为 \0 将占用一个位置)。长度为 0 的字符串被称为空串，一般使用 ∅\varnothing∅ 表示，其中只有一个 \0 。

串的匹配

在一个串中寻找指定子串是一个最常用的算法，解决方法也有多种。我们将指定的串称之为匹配串，并假设原串长度为 m，匹配串长度为 n。

朴素算法

从下标为 0 开始比较原串与匹配串，若不相同，则移位到下标为 1，直到找完原串的所有子字符串。这个算法很简单，也很好理解，其时间复杂度为 O(mn) 。

int strstr(const string& source, const string& pattern) {
  int m = source.size(), n = pattern.size();
  for (int i = 0; i + n <= m; i++) {
    bool flag = true;
    for (int j = 0; j < n; j++) {
      if (source[i + j] != pattern[j]) {
        flag = false;
        break;
      }
    }
    if (flag) {
      return i;
    }
  }
  return -1;
}

KMP 算法

KMP 实际上是三位计算机科学家的名字缩写，Knuth、Morris 和 Pratt，有意思的是，之后你还会见到 Morris 的名字，而 Pratt 的博士生导师就是 Knuth。

Knuth 1938 年生，1977 年访问中国时姚期智的夫人储枫为其取的中文名高德纳。老爷子的成就实在太多了， 计算机程序设计艺术、TeX、 METAFONT、文学式编程、LR解析理论 等等，还获得过冯诺伊曼奖与图灵奖。而老爷子是个十分有趣的人，TeX 的版本号趋近于 π 而 METAFONT 的版本号趋近于 e；为了他的著作他还开了家银行，为在他的著作中找的任何错误的人奖励 2.56 美元 (256 pennies is one hexadecimal dollar)，并对每个有价值的建议提供 0.32 美元的奖金。如今他还在十二月份安排了讲座。如果你想了解老爷子可以访问他的 个人主页。

 KMP 的主要思想是：一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置。此算法利用这一特性以避免重新检查先前匹配的字符，因此 KMP 的核心算法即求解本身包含的信息。这一信息被称为前缀函数，记作 π(i) 。对于区间 [0:i](0≤i

假设有匹配串 aabaab ，则有前缀函数

• π(0)=0 ，串 s[0:0]s[0:0]s[0:0] 没有真前缀
• π(1)=1 ，一对最长相等真前缀、真后缀为 s[0] 和 s[1] ，长度为 1
• π(2)=0 ，串 s[0:2]s[0:2]s[0:2] 没有相等的真前缀与真后缀
• π(3)=1 ，一对最长相等真前缀、真后缀为 s[0] 和 s[3] ，长度为 1
• π(4)=2 ，一对最长相等真前缀、真后缀为 s[0:1] 和 s[3:4] ，长度为 2
• π(5)=0 ，一对最长相等真前缀、真后缀为 s[0:2] 和 s[3:5] ，长度为 3

接下来就是 KMP 如何使用前缀函数，前缀函数代表了当前如果匹配失败了，在 已匹配的串 中，有多少真后缀是与真前缀相同的，那么在接下来的匹配中我们可以直接忽略这些相同的真前缀 / 真后缀，从而接着匹配字符串，跳过这些不必要的匹配。

前缀函数的实现

观察前缀函数，我们可以观察到：

• 如果 s[i]=s[π(i−1)] ，那么 π(i)=π(i−1)+1
• 如果 s[i]≠s[π(i−1)] ，那么需要递归地向前寻找
  • 当满足 s[i]=s[j],j=π(π(π(… ))−1) 时， π(i)=π(j)+1
  • 当全部不满足时，则 π(i)=0

void get_prefix_array(const string& pattern, const int len, int pi[]) {
  pi[0] = 0;
  for (int i = 1, j = 0; i < len; i++) {
    while (j > 0 && pattern[i] != pattern[j]) {
      j = pi[j - 1];
    }
    j += pattern[i] == pattern[j];
    pi[i] = j;
  }
}

KMP 的实现

我们需要利用先生成前缀数组，再对原串进行遍历匹配模式串，因此总的时间复杂度需要 O(m+n)。

int strstr(const string& source, const string& pattern) {
  int n = source.size(), m = pattern.size();
  int pi[m];
  get_prefix_array(pattern, n, pi);
  for (int i = 0, j = 0; i < n; i++) {
    while (j > 0 && source[i] != pattern[j]) {
      j = pi[j - 1];
    }
    if (source[i] == pattern[j]) {
      j++;
    }
    if (j == m) {
      return i - m + 1;
    }
  }
  return -1;
}

Sunday 算法

Sunday 算法是 BM 算法的变种，与

KMP 的核心思路一样，利用 pattern 已给出的信息，最大程度的跳过不匹配的字符。

Sunday 的思想较为简单，处理一个 pattern 偏移表，该表主要映射了 pattern 串中存在的每个字符到末尾的距离，如果有多个相同字符，则用更靠近末尾的映射替换之前的值。 Sunday 算法如果发现无法匹配，则观察这个坏字符的下一个位置的字符 c 来决定步进的长度：

1. 如果 c 不存在于 pattern 中，直接将 pattern 的起始位置与 c 的下一个字符对齐
2. 如果 c 存在于 pattern 中，则将最靠近末尾的该字符与 c 对齐

// 为实现的简便，假设 source 中只包含 ASCII 字符
int strstr(const string& source, const string& pattern) {
  int n = source.size(), m = pattern.size();
  int shift[128] = {0};
  for (int i = 0; i < m; i++) {
    shift[pattern[i]] = m - i;
  }
  for (int i = 0, end = n - m + 1; i < end;) {
    int j = 0;
    while (source[i + j] == pattern[j]) {
      ++j;
      if (j == m) {
        return i;
      }
    }
    i += shift[source[i + m]] == 0 ? m + 1 : shift[source[i + m]];
  }
  return -1;
}