|
子串定位运算 串是特殊的线性表故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似 C语言的串库里提供了丰富的串函数来实现各种基本运算因此我们对各种串运算的实现不作讨论利用串函数实现 串的基本运算部分内容【参见练习】 下面讨论在顺序串和链串上实现的子串定位运算 子串定位运算 子串定位运算类似于串的基本运算中的字符定位运算只不过是找子串而不是找字符在主串中首次出现的位置此运算的应用非 常广泛 【例】在文本编辑中我们经常要查找某一特定单词在文本中出现的位置解此问题的有效算法能极大地提高文本编辑程序的 响应性能 子串定位运算又称 串的模式匹配 或 串匹配 目标(串)和模式(串) 在串匹配中一般将主串称为 目标(串) 子串称为 模式(串) 假设T 为目标串P为模式串且不妨设 T=t t t …t n P=p p p …p m ( 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中所有出现的有效位移。 |
