间隙字符串算法.ppt

间隙字符串匹配问题 .问题描述： 假设允许模式串t 中可以出现能与任意字符串（包括长度为0 的空串）匹配的间隙字符◇。例如串”ab◇ba◇c”，可在主串”cabccbacbacab” 产生如下匹配： (1) cabccbacbaab ab◇ba◇c (2)cabccbacbacab ab◇ba◇c 设间隙字符◇可在模式串中出现任意多次，但不允许在主串中出现。试设计一个算法确定这样的间隙模式串t 是否产生主串s 中的一个匹配。 编程任务： 给定主串s 和间隙模式串t，编程计算间隙模式串t 在主串s 中的匹配。 数据输入： 由文件input.txt 给出输入数据。第1 行是主串s；第2 行是间隙模式串t，其中间隙字符◇用字符’*’表示。 结果输出: 将计算结果输出到文件output.txt 。当间隙模式串t 产生主串s 中的一个匹配时输出 “Yes”，否则输出“No”。 输入文件示例输出文件示例 input.txt output.txt cabccbacbacab Yes ab*ba*c 我的方法:不修改KMP算法,以*为间隔,将间歇模式串t分割成若干子串并逐个与主串进行匹配. 流程图: JUDGE: if(j!=0) outYes; else outNo; 例: input.txt cabccbacbacab ab*ba*c S1: cabccbacbacab S2: ab*ba*c 此时i=3 S3: ab j=2 S1:ccbacbacab S2:ba*c 此时i=3 S3: ba j=3 S1:cbacab S2:c 不足之处: 1:该算法对于间歇子串有一定局限性.即间歇字符*不能出现在子串的开头,结尾.以及子串中不能有连续的*出现. 例如:cabccbacbacab **ab***ba*c * 从题意可知例题满足匹配,但是如用此算法便不能得到正确答案. 2:调用辅助空间S3,增大了空间复杂性. 改进方法: 1:使用朴素的模式匹配算法,在遇到*的时候i不变j向后跳过一位.并记录下此时的j=jm,如遇到不匹配的情况, i要返回i-j+2+(jm-1),j返回jm. 此方法虽然可以解决*的问题 ,但是由于使用的是朴素算法,使得该算法的时间复杂性不是太好. 2:在S2读入时进行处理,遇到连续的*以及串首,尾的*时将其删除,使之成为例题中的ab*ba*c模式. 3:每次进行KMP匹配之后,将主串回溯到i+j-1,就不需要使用delete函数对主串的前i+j-2项进行删除了,可以节省时间 THANK YOU! * * 建立3个串S1,S2,S3,从input.txt读取主串S,模式串t,分别赋于串S1,S2 定义 int i=0,j;i为*位置,j为子串对主串的匹配位置 While(i!=-1) 寻找出b中*位置,将*前字符串赋于c,并求c与a的匹配 i=s2.Find(*,1); s3=s2.SubStr(1,i-1); j=s1.Match(s3); j=0? YES,跳出循环,GOTO JUDGE NO, 删除s2前i个元素,删除s1的前i+j-2个元素,并且继续寻找* 循环结束后,将剩余串S2与S1进行匹配,得到j,并且GOTO JUDGE 从题目可以看出,本题显然输出YES.下面让我们从例题着手,对算法进行分析 删除s2前i=3个元素,删除s1的前i+j-2=3个元素,并且继续寻找* 删除s2前i=3个元素,删除s1的前i+j-2=4个元素,并且继续寻找* 此时S2中无*,i=-1,跳出while循环 j=s1.Match(s2)=1 进入JUDGE, j!=0,输出Yes 对于本题与该算法的一些想法 *