串思维导图

即字符串（string）由0个或多个字符组成的有限序列；

术语：串长、空串、子串、主串、字符在主串中的位置、子串在主串中的位置

串的数据对象为字符集

串的基本操作大多以子串为操作对象

Index(S,T)：找到串T在主串S中的位置

StrCompare(S,T)：比较操作，若S>T，返回＞0；S=T返回0；S<T，返回＜0

SubString(Sub,S,pos,len)：求子串，从pos起长度为len的子串；

rep(T,P,S)：将T中所有出现的P都替换成S的运算

concatstr(S,T)：S后面接上T

主串长度n，模式串长度m

将主串中所有长度为m的子串与模式串比较

找到第一个与模式串匹配的子串并返回起始位置

若都不匹配返回0

最坏时间复杂度：O(mn)，此时每个子串都对比了m个字符，前面都相同就最后字符一个不同

朴素模式匹配代码，重点在于i = i - j + 2，因为这里i从1开始，如果从0开始是+1

循环也可以修改为while(i<=m-n&&j<n)，最后循环结束判断改为if(i<=m-n && j==n)

无论是BF模式匹配还是KMP算法，当失配时，一趟结束，确定好新的匹配位置时新的一趟开始

先根据模式串T求出next数组，next数组只和模式串有关与主串无关

利用next数组进行匹配

利用next数组，KMP模式匹配算法

匹配成功（j超过模式串长度），返回i - 模式串长度，即为第一个子串出现位置

求next数组时间复杂度O(m)

模式匹配时间复杂度O（n）

总时间复杂度O(m + n)

主串指针i不用回溯

手算求next数组

算法思路

代码求next数组

基本思路：列出如上next表格，看j对应的模式串字符和next[j]对应的模式串是不是相等，一旦相等，就把next[j]改为next[j]所对应的next[j]，即nextval[next[j]]

代码实现时，在i++，j++后再次判断T[i]和T[j]，如果不相等就nextval[i] = j；否则nextval[i] = nextval[j]；

静态数组实现

动态数组实现

各结点存一个字符：存储密度低

各结点存储多个字符