数据结构算法的定义 串 - 串的存储结构 - 串运算的实现（一）

串 - 串的存储结构 - 串运算的实现（一）  

　　子串定位运算

　　串是特殊的线性表 故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似

　　C语言的串库 里提供了丰富的串函数来实现各种基本运算 因此我们对各种串运算的实现不作讨论 利用串函数实现

　　串的基本运算部分内容【参见练习】

　　下面讨论在顺序串和链串上实现的子串定位运算

　　 子串定位运算

　　子串定位运算类似于串的基本运算中的字符定位运算 只不过是找子串而不是找字符在主串中首次出现的位置 此运算的应用非

　　常广泛

　　【例】在文本编辑中 我们经常要查找某一特定单词在文本中出现的位置 解此问题的有效算法能极大地提高文本编辑程序的

　　响应性能

　　子串定位运算又称 串的模式匹配 或 串匹配

　　 目标(串)和模式(串)

　　在串匹配中 一般将主串称为 目标(串) 子串称为 模式(串)

　　假设T 为目标串 P为模式串 且不妨设

　　T= t t t …t n

　　P= p p p …p m ( ≤n)

　　3、串匹配

　　串匹配就是对于 合法的位置 (又称合法的位移)0≤i≤n-m，依次将目标串中的子串"t i t i+1 …t i+m-1 "和模式串"p 0

　　p 1 p 2 …p m-1 "进行比较：

　　①若"t i t i+1 …t i+m-1 "="p 0 p 1 p 2 …p m-1 "，则称从位置i开始的匹配成功，或称i为 有效位移 。tW.WiNGWit.CoM

　　②若"t i t i+1 …t i+m-1 "≠"p 0 p 1 p 2 …p m-1 "，则称从位置i开始的匹配失败，或称i为 无效位移 。

　　因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。

　　注意：

　　有些应用中要求求出P在T中所有出现的有效位移。