数据结构-串.pptVIP

Chapter 4String 例如: 设s=abacabab,t=abab,第一次匹配过程如下所示。 此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹配。因t0≠t1,s1=t1,必有s1≠t0,又因t0 =t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接从i=3,j=1开始。 第1次匹配 s=s0s1s2s3s4s5s6s7 i=3 t = t0 t1 t2 t3 j=3 第1次匹配 s=a b a c a b a b i=3 t=a b a b j=3 失败 为此,定义next[j]函数如下: max {k|0kj,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1” } 当此集合非空时 -1 当j=0时 0 其他情况 next[j]= 1 0 0 -1 next[j] b a b a t[j] 3 2 1 0 j t=“abab”对应的next数组如下: 第1次匹配 s=a b a c a b a b i=3 t=a b a b j=3 失败 例: 设目标串s=“acabaabaabcacaabc”,模式串t=“abaabcac”。s的长度为17,t的长度为8。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置。KMP模式匹配过程如下所示。 1 b 4 2 c 5 0 a 6 1 1 0 0 -1 next[j] c a a b a t[j] 7 3 2 1 0 j 1 b 4 2 c 5 0 a 6 1 1 0 0 -1 next[j] c a a b a t[j] 7 3 2 1 0 j 第1趟 目标串 模式串 a c a b a a b a a b c a c a a b c a b a a b c a c i=1 j=1 next(1)=0 第2趟 目标串 模式串 a c a b a a b a a b c a c a a b c a b a a b c a c i=1 j=0 next(0)=-1 1 b 4 2 c 5 0 a 6 1 1 0 0 -1 next[j] c a a b a t[j] 7 3 2 1 0 j 第3趟 目标串 模式串 a c a b a a b a a b c a c a a b c a b a a b c a c i=2 j=0 j=5 next(5)=2 i=7 第4趟 目标串 模式串 a c a b a a b a a b c a c a a b c a b a a b c a c i=7 j=2 i=13 j=8 int KMPIndex(String s, String t) { int next[MaxSize],i=0,j=0,v; GetNext(t,next); while (is.slen jt.slen) { if (j==-1) { i++; j=0; } else if( s.data[i]= =t.data[j] ) { i++; j++; } // i,j各增1 else j=next[j]; // i不变,j后退 } if (j=t.slen) v=i-t.slen; //返回匹配模式串的首字符下标 else v=-1; //返回不匹配标志 return v; } KMP算法 1、理解串的定长顺序存储、堆存储及链式存储各自的优缺点，能在应用中进行合理的选择。 2、掌握串的堆存储结构及其实现串的各种操作的基本方法。 教学要求 4、理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值。 3、理解串匹配中简单算法的匹配过程及其具体实现。 空串也认为是S的子串 不重叠指的是直接从主串中查找所有对应的子串并进行替换，而不是替换一