挖矿网站怎么免费建设,广州网站建设哪家便宜,网站建设三个友好,网络推广器串 目录
串
一、串#xff1a;
二、串的存储结构#xff1a;
三、模式匹配
1.简单模式匹配#xff08;BF算法#xff09;
2.KMP算法
2.1-next#xff08;j#xff09;数组手工求解
2.2-nextval#xff08;j#xff09;数组手工求解 一、串#xff1a;
内容受…串 目录
串
一、串
二、串的存储结构
三、模式匹配
1.简单模式匹配BF算法
2.KMP算法
2.1-nextj数组手工求解
2.2-nextvalj数组手工求解 一、串
内容受限的线性表也就是相当于C语言里的字符串只不过这里字符串从1开始存取。
此外串里包含子串每个字串的第一个元素位置为该字串在串中的位置每个串里面必有一个空串此外数串的时候遇到重复的只保留一个。
kmp算法就是根据相应的字串模式串取查找相应位置的操作
串的长度实际上为字符串长度。而数组长度为串的长度11从数组1开始存因此1最后字符串结尾\0’也要存。
二、串的存储结构
静态顺序存储就是定义一个固定长度的字符数组再多一个记录个数的变量。
堆分配存储就是动态数组malloc一个空间空间大小为sizeofchar*(max2);
块链存储就是单链表的基础上多了好多存储数据的变量因此一块结点好几个变量存进去。
串的基本操作 SteCompare(S,T),就是C语言里的字符串比较实际操作为S-T若结果小于0则ST若结果大于0则S大于TS、T为字符串。
Concat(*T,S1,S2),给S2连接到S1后面组成新的串赋值给T串返回。
SubStrin(*Sub,S,pos,len)返回串S中第pos位置起长度为len的字串
IndexS,T,Pos模式匹配S中第pos位置起与字串T相等的串。并返回该串再S中出现的第一次的位置。
三、模式匹配
1.简单模式匹配BF算法
模式匹配就是有一个字串模式串取对应的主串里找与它一样的并返回它在主串中的位置
简单模式匹配就是主串在上模式串在下动主串坐标取挨个对比。
设i为记录主串的下标j为模式串的下标k则是记录每次回溯比对的次数。
当i和j中的值都相等时都往后移动当不匹配时则进行下标的更新主串中的i更新为ik1即主串的i从左至右挨个比对第一个开始比对失败则第二个开始重新比对。模式串则时更新为j1因为每次重新比对所以模式串每次更新都是从1开始。
简单模式匹配算法为m*n,主串长为m模式串为n因为最坏的情况每次主串都要重新比对所以为m而每次比对模式串都需要从头到尾重新遍历所以m*n
2.KMP算法 kmp时间复杂度为OmnKMP算法主要是模式串下标动更新主串中的i会一直增加不会出现回溯的现象。
2.1-nextj数组手工求解 在简单模式匹配的基础上优化。即nextj数组是记录每次模式串比对失败时模式串下标的更新的起始值。如果模式串下标j0则ij即简单匹配操作否则主串不需要动模式串下标更新动即可。 而next(j)数组怎么求嘞next数组就是给模式串每一个位置处匹配失败时跟新的下标值都记录下来。所以手工怎么计算呢 分两部分当第一个位置处时j直接更新为0因为第一个位置前无数据没法拿来进行找重复部分的长度。第二个位置时则找第一个位置然后错一位进行比对比对时下面的那一串向右移动直到比对完重复部分之后重复部分长度1便是模式串下标所更新的值。
具体看讲义不好画图
2.2-nextvalj数组手工求解 nextval数组则是在next的基础上再优化。即当next数组求的坐标的内容与原来不匹配的坐标内容一致时可直接给nextval中当前不匹配情况与所求最新的坐标相同即可。
具体看讲义不好画图。
