串的定义
是由零个或多个字符组成的有限序列
存储
顺序存储
静态数组
动态数组
链式存储
可以每个结点存多个字符，没有字符的位置用‘\0‘补足 链式存储，存储密度很低
基本操作
比较
找子串
串和线性表的区别
可以从数据结构的三要素展开论述
区别
串的数据对象限定为字符集
串的基本操作大多以子串为操作对象
相同
-
都是线性结构
字符串模式匹配
在主串中找到与模式串相同的子串，并返回其所在位置
朴素模式匹配算法
思想：
将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止
最多对比 n-m+1个子串（考试考过！！）
性能：O(m*n)
KMP算法
思想
根据模式串求出next数组，利用next数组进行匹配（主串指针不回溯）
性能：O(m+n)
其中，求next 数组时间复杂度O(m)，模式匹配过程最坏时间复杂度O(n)
重点掌握next数组的手算求法
若出现当字符串不匹配时的位置为i，模式串向后移动，只要出现模式串的前缀和主串i前的字符串能匹配上，则模式串在i前包括i有几个字符串，下标就为几
求next数组例题：
next[1]和next[2]分别是0和1，
比如出现第6个字符不匹配时，模式串向后移动，直到部分能和主串匹配就停下来，如上图，因为？可能和b匹配，因此next[6]的值为 4.其他的值也可以自己手动算一下试试。
求出next数组后，如果遇到第一个字符不匹配，则特别要注意next[1]这种情况：
即要把模式串的指针定义为0,（此时的j的合法范围是从1开始，如果是从0开始，则j此时要定义为-1），然后i++,j++。即主串移动指针，子串也要移动指针。
那么问题来了，比如考研复试某真题：KMP算法，什么情况下主指针需要向前移动？
答案：当第一个字符串不匹配的时候，即next[1]=0，此时需要移动主串的指针，只需移动一个单位，同时模式串的指针也要移动一个单位，以恢复到合法的指针范围。
