串
一.定义
子串 主串 空格串≠空串 Φ
堆式顺序储存结构
二. 匹配：
1.库函数 strstr (C++/C
返回字串头指针 /null （一个一个向前挪地比较
T = O（n*m） 最坏情况 最后一个字符不同
2.改进-----从末尾开始比
幸运：T = O（n） T = O（n*m） 最坏情况 第一个字符不同
3.KMP算法
T = O（n）
找到相同子串 
三. 数组
三维数组
LOC(a47)=LOC(a00)+(j*m+i)*L=SA+(7*8+4)*3=SA+180
13、设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：(B)
A. 9
B. 10
C. 12
D. 15
解析：
求next数组，next={-1,0,0,1,1,2};
开始匹配
abaabaabcabaabc
abaabc
当比较到s[5]时，不成功，比较6次；
abaabaabcabaabc
-----abaabc
根据next[5]=2，移动S到S[2]处，从S[2]处开始比较，比较4次，成功；
一共比较10次
（原文链接：https://blog.csdn.net/weixin_43751983/article/details/103370761）
五. 实践小结
pta求交集那题 1 先顺序再求交集
2 位图法 （最后没过的那个测试点是各有100000个数 那我一开始记录的数组就要大一点了
位图法就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。---百度解释
位图法应用
使用位图法判断整形数组是否重复
使用位图法进行整形数组排序
图源 https://blog.csdn.net/yangquanhui1991/article/details/52172340
原文：https://www.cnblogs.com/drgnibasaw/p/12785809.html