串是由零个或多个字符组成的有限序列，又名叫字符串；零个字符的串称为空串(null string，也用Φ表示)，只包含空格的串称为空格串，串中的子序列称作子串 串的比较：以ASCII码为字符集；比较对应位置的值和长短
存储结构
顺序存储结构：用普通方式实现会产生很多问题，因此要做变化：串值的存储空间可在程序执行过程中动态分配而得 链式存储结构：一个结点可以存放一个或多个字符，若末尾结点未满则用”#”或其他非串值字符补全
- 串的链式存储在连接串与串操作时有一定方便，但总的来说不如顺序存储灵活，性能也没它好
朴素的模式匹配算法
子串的定位操作通常称作串的模式匹配 思路：对主串的每一个字符作为子串开头，与要求匹配的字符串进行匹配，对主串做大循环(循环回溯主串下标)，每个主串字符开头做子串长度的小循环，直到循环结束 时间复杂度：
- 最好：O(1)
- 平均：O(n+m)
- 最坏：O((n-m+1)*m)
KMP模式匹配算法
朴素的模式匹配算法很低效，所以有了一个模式匹配算法可以避免重复遍历的情况，我们把他称为克努特—莫里斯—普拉特算法，简称KMP算法
- 原理：不让没必要的回溯发生，检查子串的结构中是否有重复，若重复可以省略一部分不必要的判断步骤；根据前后缀相似度来决定匹配操作
- 把子串各位置的j值(即下标)的变化定义为一个数组next，数组的长度就是子串的长度，由此可得：
next[j] = 0，当j=1时
= Max{ k| 1<k<j，且'P1···Pk-1'='Pj-k+1···Pj-1' } 当此集合不空时 # 此行P后面的数字及kj都是下标
= 1，其他情况
推导：T(子串)='abcabx'
当j=1时，next[1]=0;
当j=2时，j由1到j-1只有字符'a', next[2]=1; # 属于其他情况
当j=3时，'ab', next[3]=1;
当j=4时，'abc', next[4]=1;
当j=5时，'abca', 可推算出k为2(P1=P4), 因此next[5]=2;
当j=6时，'abcabx', next[6]=3;
结果即next[j] = 011123
如果前后缀一个字符相等, k值是2, 两个字符k值是3, 前后缀n个字符相等k值就是n+1
- 思路：得到子串的next数组；限定条件使下标在长度范围内进行循环；比较子串(下标j)和主串(下标i)字符，相等就继续(且满足j=0)，否则j退回合适的位置(i是不变的)；最后返回位置或0(即不存在)
- 与朴素匹配算法比较：去掉了i值回溯的部分；使得子串循环部分的大O由O(m)变为O(n)(m为子串长，n为主串长)，因此整个算法的时间复杂度为O(n+m)，但KMP与朴素匹配差异并不明显，除非是模式与主串之间存在许多”部分匹配”时
- KMP算法的改进(数组nextval)：计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next的值