串

串的基本概念

  1. 串是特殊的线性表，存储的是字符
  2. 空串与空格串含义不同，空串长度为0，空格串是含有空格的串
  3. 子串是任意多个子序列组成的串，子串的位置就是其首个字符在串中的位置
  4. 串相等就是所有字符都一一对应相等
  5. 串一般使用顺序存储
  6. 表示串的长度一般用结束符，如’\0’
  7. C++ 字符串函数
    • 求串长
    • 串赋值
    • 串连接
    • 串比较
    • 是否为子串
    • 截取串
    • 串插入
    • 串删除
    • 用子串替代另一个子串
    • 输入字符序列
    • 输出字符序列
  8. string.h(可以直接使用)
    • 串长度 int strlen(char *str)
    • 串拷贝　char *strcpy(char *str1，char *str2)
    • 串连接　char *strcat(char *str1，char *str2)
    • 串比较　char *strcmp(char *str1，char *str2)
    • 串中字符定位char *strchr(char *str , char ch)

模式匹配算法

模式匹配定义：从一个主串中找查找一个字符串

Brute-Force算法

不动脑子的暴力算法，就是将主串和被查找串进行一一对比，如果不一样就主串查找的计数器要返回到最初的位置的后一位。这种算法是要返回主串计数器，计算次数较多，时间复杂度为O(n*m)
设主串计数器为i,被查找串计数器为j。当j>=被查找串长时找到被查找串。如果j<被查找串长且i>=主串长，则主串没有被查找串。

KMP算法

与BF算法不同的是KMP算法的主串计数器不会返回，它只会一路往前，这就使得它的复杂度变小，KMP算法的时间复杂度为O(n+m)。KMP需要计算失效函数来确定被查找串的回溯距离。
失效函数如下：

失效函数利用公共前后缀来得到被查找串回溯的距离，对于任何一个字符串，失效函数第一位一定是-1，第二位一定是0，失效函数看的是上一位的情况。

优化的失效函数

为什么要优化KMP算法？
优化的失效函数如下：

根据上述函数可知，优化的失效函数基于失效函数。在字符和以失效函数为下标的字符不等或者j=0时优化的失效函数和失效函数一致；当字符和以失效函数为下标的字符相等并且j≠0时，失效函数进行迭代，直至找到j=0或者字符与以失效函数下标字符不等的情况。
普通的失效函数比较的是之前串中前缀后缀的相同的数量，而优化的失效函数比较的是当前的字符。