串，即字符串，是由零个或多个字符组成的有限序列

串是一种特殊的线性表，数据元素之间呈线性关系

如果串长为n，则其子串个数为n(n+1)/2+1个，真子串个数为n(n+1)/2个。

每个英文字符占1个字节。中文字符ASCII码占1个字节，UTF8站3个字节

乱码产生原因：编码规则错误，映射集错误

链式存储实现串时，一个字符1B，一个指针4B，存储密度低，可以考虑每个结点4字符+1指针

设有两个字符串T和pat，在串T中查找是否有与串pat相等的子串，称串T为【目标】（Target），串pat称为【模式】（Pattern）。

称查找模式在目标中的匹配位置的运算为模式匹配（Pattern matching）。

朴素模式匹配算法：主串长n，模式串长m。从主串中依次取出长度为m的子串和模式串进行对比，直到找到一个完全匹配的子串（最多对比n-m+1个子串）。最坏的时间复杂度，每次对比都对比到最后一个字符：O(nm)；最好的时间复杂度，每次对比在第一个字符就判断出不对：O(n)。

KMP算法：next数组：当第x个元素匹配失败时，令模式串指针j指向第y个元素next[x]=y

根据模式串T，求next数组，利用next数组进行匹配（主串指针不回溯）

最坏时间复杂度，next数组时间复杂度(预处理)m，模式匹配过程最坏时间复杂度n：O(m+n)

求模式串的next数组：next[1]=0；next[2]=1；其他next：在不匹配的位置前，划一根分界线，模式串一步步后退，直到分界线之前能对上，或模式串完全跨过分界线为止。此时j指向哪儿，next数组值就为多少。