Skip to main content

串

定义​

tip

字符串简称串，零个 或多个字符组成的有限序列，串中任意多个连续的字符组成的子序列被称为该串的子串，包含字串的串被称为主串。

串可以视为线性表的限制——数据对象为字符，此外二者在操作上有较大区别，串通常以子串为操作对象。

存储结构​

可以使用一个字符数组来表示，但是要额外存储字符串的当前长度，或者使用一个隐含的结束标记 \0.

也可以使用结构体存储字符串的长度和首地址，这样可以实现一个可变长度的字符串——每次操作后都销毁并重建。

采用链表的方式存储，由于字符串的性质，每个节点可以存储多个字符，因此也被称为 块链结构。

串的模式匹配​

tip

子串的定位操作被称为 模式匹配，其求的是字串在主串中的位置。

暴力算法​

最常规的算法是从主串的每个位置开始向后进行匹配，计算冗余较大。

最坏情况

主串类似 AAAAAA…AB，子串类似 AAAAB.

KMP 算法​

暴力算法中每次匹配失败时子串的指针的都要进行回溯，这导致了其时间复杂度是 O(mn)O(mn) 的，kmpkmp 算法是一种线性的子串匹配算法，原则是由于已经知道读取过那些字符了，因此就不再需要回溯到子串的开头。

举个例子

假设主串是 ABABABCAA，子串是 ABABC.

    ↓
ABABABCAA
    ↓
ABABC

最开始的条件下，当指针匹配到第五个元素时会失败，但是由于之前已经遍历了主串的 ABAB，显然可以直接将子串移动到第二个 AB 中

    ↓
ABABABCAA
    ↓
  ABABC

再继续向后匹配即可。

但是如何得知子串应该向后移动多少呢？kmpkmp 算法中需要一个 next 数组来表示，本例中如下：

ABABC
00120

当匹配失败时，查看 最后一个匹配的字符 所对应的 next 数值，因此移动子串跳过主串中的两个字符，同时子串中的字符也跳过两个，指向第三个字符。

如何构造 next 数组

next 数组实际上表示的是 子串的子串 的共同前后缀的最大长度，上例中对于第四个字符 BB 来说，子串的子串 ABAB ，其共同前后缀 AB 长 22，即是其 next 数组对应的值。

info

这样也就能解释为什么主串的指针不会后退，且子串可以跳过匹配一些字符了。

因为在主串指针之前除去公共后缀的部分是一定不会被匹配成功的，只有在公共后缀开头的部分才能继续匹配，而前后缀相同，因此子串中可以直接跳过，这就导致了主串指针不需要回溯。以上面的例子来说：

    ↓
ABABABCAA
    ↓
ABABC

公共后缀是 AB （因为这部分已经匹配成功了），则 AB 之前的字符不需要在匹配了，这时可以从第三个字符开始匹配，而前后缀是相同的，因此直接跳过即可。

caution

前后缀的最大长度都是字符串的长度减去一。

next 数组即公共前后缀的计算方式如下：

第一字符的 next 值一定为 00；

如果当前字符和前一字符所对应的前缀的后一个字符相同，则当前字符的 next 值为前一字符的 next 值加 1 ，例如

     ↓
ABACABAB
00101

这里指向 B，则前一个字符的 next 值是 11，则直接查看 next 数组的第一个元素与当前元素是否相同，相同则加一。

若当前字符和前一个字符所对应的前缀的后一个字符不相同，则通过回溯的方式查看前缀的后一个字符是否相同

warning

这里没太搞懂原因，先留个坑，总之体现在代码上就是

len=next[len-1]
           ↓
ABABABABABAC
00123456789

待续…

caution

在编写代码的过程中，要尤其注意第一个字符匹配就失败的情况，这是需要移动主串指针，主串指针只会在匹配成功或这第一个字符匹配失败的情况的下移动。

代码如下

void build_next(char *str, int *next) {
  int i = 1, len = 0, cur_idx = 1;
  next[0] = 0;
  while (str[i] != '\0') {
    if (str[i] == str[len]) {
      next[cur_idx++] = len++;
      i++;
    } else if (len == 0) {
      next[cur_idx++] = 0;
      i++;
    } else {
      len = next[len - 1];
    }
  }
}

int kmp(char *str, char *substr, int *next) {
  int i = 0, j = 0;
  while (str[i] != '\0') {
    if (substr[j] == '\0')
      return i - j;
    if (str[i] == substr[j]) {
      i++;
      j++;
    } else if (j > 0) {
      j = next[j - 1];
    } else {
      i++;
    }
  }
  return -1;
}

caution

朴素的模式串匹配算法没有利用已知信息，导致时间复杂度大大增加；而 KMP 算法只是针对模式串的一种类型进行优化，即模式串中有公共前后缀，如果模式串中每个元素都是独一无二的，则其退化为朴素算法。

caution

这里的 next 数组和考研中的不太一样，需要将这里的数组整体向右移动一位，因为最后一位是用不上的，直接舍去即可，而空出来的第一位是用 -1 代替，并对数组整体加一。

KMP 的改进算法​

当模式串有连续字符时，如 aaaab，next 为 01230，当其在最后一个 a 匹配失败时，根据匹配算法，会继续用前面三个 a 继续匹配，但显然是没有必要的。

待续…

反正 nextvalnextval 数组需要根据 next 数组确定，如

         1 2 3 4 5 6 7 8
         a b a b a c a b
         0 0 1 2 3 0 1 2   右移加一
next:    0 1 1 2 3 4 1 2   next值对应下标的字符和当前下标不同直接抄下来，相同则抄对应下标字符的nextval值，先找不同：
nextval: 0 1       4       再找相同：
         0 1 0 1 0 4 0 1