2018-03-23 串（字符串）

        串（string）是仅有字符组成的特殊的线性表，分为顺序存储和链式存储。字符串有很多重要的操作，赋值，求长度，连接，求子串，删除，定位，替换等。字符串一般不用来比较大小，而是用于来比较是否相等。

串的匹配：

BF（bruce force）算法复杂度可以到O(m*n)效率低

KMP模式匹配算法，S表示主串，T表示子串，匹配的时间复杂度只与子串有关，而与主串无关。其中的核心在于存在一个next数组， next数组用于生成下一次匹配索引，next数组的生成只与子串本身的结构有关，根据失配位置，判断前缀和后缀相同的数量。前后缀判断是从中切开，看两边的字符是否相同，奇数直接丢弃。

无前缀               填0 
只有前缀           填1
前缀后缀不同    填1 
前缀后缀相同    填2  （前后缀长度+1）

注意：前缀是固定的，后缀是相对的