第4章-数据结构第3版- 串、数组和广义表-2024秋.pptx

;;;;;串的定义;a=‘BEI’,

b=‘JING’

c=‘BEIJING’

d=‘BEIJING’;;研究人员不断从苹果、桑树等树种中检测到新的双生病毒;案例引入--病毒感染检测;;;;案例引入--模式匹配算法;模式匹配算法应用--网络入侵检测;模式匹配算法应用--网络入侵检测;模式匹配算法应用--网络入侵检测;;模式匹配算法应用--网络入侵检测;模式匹配算法应用--信息检索;;模式匹配算法——Index(S,T,p);;串的类型定义、存储结构及运算;(5)SubString(Sub,S,pos,len)//求子串

(6)StrCopy(T,S)//串拷贝

(7)StrEmpty(S)//串判空

(8)ClearString(S)//清空串

(9)Index(S,T,p)//子串的位置

(11)Replace(S,T,V)//串替换

(12)StrInsert(S,pos,T)//子串插入

(12)StrDelete(S,pos,len)//子串删除

(13)DestroyString(S)//串销毁

}ADTString;串的存储结构;;;#defineCHUNKSIZE80//可由用户定义的块大小

typedefstructChunk{

charch[CHUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{

Chunk*head,*tail;//串的头指针和尾指针

intcurlen;//串的当前长度

}LString;;优点：操作方便

缺点：存储密度较低;串的模式匹配算法;S:ababcabcacbab

T:abc;BF算法步骤;;;;;;;案例实现--病毒感染检测;依次检测每对病毒DNA和人的DNA是否匹配，循环执行：

分别读取一对病毒DNA序列和人的DNA序列；

设置flag，初始为0，表示未匹配；

病毒DNA长度是m，连续存储两次扩大为2m；

循环m次，重复执行以下操作：

依次取得每个长度为m的病毒DNA环状字符串；

将此字符串作模式串，将人的DNA作主串，调用BF，将结果返回flag；

若flag非0，表示匹配成功。

退出循环时，若flag非0，输出“YES”，否则，输出“NO”。;案例实现--病毒感染检测;医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的DNA序列都是环状的。现在研究者收集了大量的病毒DNA和人的DNA数据，想快速检测出这些人是否感染了相应的病毒。为方便研究，研究者将人的DNA和病毒的DNA均表示成由一些小写字母组成的字符串，然后检测某种病毒的DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了病毒，否则没有感染。注意：人的DNA序列是线性的，而病毒的DNA序列是环状的。;案例实现--网络入侵检测;随着互联网的飞速发展，网络安全问题日益严重。入侵检测技术是一种积极主动防御的安全保障技术，而Snort是其中基于规则匹配的一种入侵检测技术。Snort自1998年被发明以来，历经数年的迭代更新，Snort已成为一个具有多平台(Multi-Platform)、实时(Real-Time)流量分析、网络IP数据包(Pocket)记录等特性的强大的网络入侵检测/防御系统(NetworkIntrusionDetection/PreventionSystem)，即NIDS/NIPS。

Snort首先需要使用者根据入侵行为的特征，按照一定的规范将这些特征编写成规则，最后通过检测网络数据与规则数据库中的规则是否匹配来判断入侵与否。在Snort入侵检测系统中，规则的匹配效率是影响Snort检测效率的关键。而规则匹配的核心技术是模式匹配算法。

请实现一个模式匹配算法，用于网络入侵行为的检测。若检在网络日志中检测到任何一条检测规则中的ip地址，则输出“Networkintrusiondetected.”，反之输出“Nothingdetected.”;输出一行，若在网络日志中检测到任何一条检测