数组、串与广义表.ppt

第四章 主要内容 用KMP算法实现的快速匹配算法 int AString::fastFind(AString pat, int k, int next[]) { int posP = 0, posT = k; //两个串的扫描指针 int lengthP = pat.curLength; //模式串长度 int lengthT = curLength; //主串长度 while (posP lengthP posT lengthT) if (posP == -1 || pat.ch[posP] == ch[posT]) { posP++; posT++; } //对应字符匹配 else posP = next[posP]; //求pat下趟比较位置 if (posP lengthP) return -1; //匹配失败 else return posT-lengthP; //匹配成功 }; * 示例 主串T: a c a b a a b a a b c a c a a b c 模式串P: * j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 a b a a b c a c posT posP 示例 主串T: a c a b a a b a a b c a c a a b c 模式串P: * j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 a b a a b c a c posT posP 示例 主串T: a c a b a a b a a b c a c a a b c 模式串P: * j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 a b a a b c a c posT posP 示例 主串T: a c a b a a b a a b c a c a a b c 模式串P: * j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 a b a a b c a c posT posP 示例 主串T: a c a b a a b a a b c a c a a b c 模式串P: * j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 a b a a b c a c posT posP posP=lengthP 设模式 P = p0p1...pm-2pm-1，next特征向量定义： 示例 j 0 1 2 3 4 5 6 7 P a b a a b c a c next(j) -1 0 0 1 1 2 0 1 * 求next[j]的函数 以前面的例子说明： j 0 1 2 3 4 5 6 7 P a b a a b c a c next [j] -1 0 0 1 1 2 0 1 * j=4 k=1 p3?p1 k=nk=0 p3=p0 n4= =k+1 =1 j=3 k=0 n3= =k+1 =1 j=2 k=0 p1?p0 k=nk= =-1 n2= =k+1 =0 j=1 k=-1 n1= =k+1 =0 j=0 n0=-1 j=5 k=1 p4=p1 n5= =k+1 =2 j=6 k=2 p5?p2 k=nk=0 p5?p0 k=nk=-1 n5=k+1=0 j=7 k=0 p6=p0 n7=k+1 =1 对当前串计算next特征向量的算法 void AString::getNext(int next[]) { int j = 0, k = -1, lengthP = curLength; next[0] = -1; while (j lengthP) //计算next[j] if ( k == -1 || ch[j] == ch[k]) { j++; k++; next[j] = k; } else k = next[k]; }; * 课堂练习 * 主串T: a c a b a a b a a b c a c a