第七章 字符串匹配.pptVIP

BM算法的基本要点是： (1)对正文中可能出现的每个字符根据该字符在模式中的出现位置，定义函数d，并用数组d[]存储对应字符的函数值。 (2)确定正文某段字符列是否能与模式匹配的字符比较顺序是从模式的最后一个字符开始自右向左逆序比较。 (3)一旦发现正文的某字符与当时模式中的对应字符不匹配时（不管在什么位置），则下一步比较的开始位置是模式m-1，正文i+d(ti)，并继续自右向左逆序比较。 下面举例说明BM算法的匹配过程。设模式字符串P=”abdcabdc”，首先由模式P确定各字符的d函数的值如下： d(‘a’)=3，d(‘b’)=2，d(‘c’)=4，d(‘d’)=1， d(其它字符)=8。 图7.3展示了两个BM算法字符串匹配的过程。 【函数7.5】 计算d的函数 void calculateD(int d[ ], char *p, int m) { int k; for(k = 0; k 256; k++) d[k] = m; for(k = 0; k m-1; k++) d[p[k]] = m-k-1; for(k = 0; k m; k++) printf((%c:%d), p[k], d[p[k]]); printf(\n); } 【函数7.6】 BM字符串匹配函数 char *bmMatch(char *t, char *p) { int k, j, i, m = strlen(p), n = strlen(t), d[256]; calculateD(d, p, m); i = m-1; do { j = m-1; k = i; while(j = 0 p[j] == t[k]) { j--; k--; } if (j 0) return t + i - m + 1; i = i+d[t[i]]; }while (i n); return NULL; } 上述计算d的算法的运行时间为Θ(m)，BM算法的最坏情况在每轮匹配比较了m个字符后才失败的情况下发生，运行时间为Θ(mn)。 7.4字符表达式匹配 在字符串匹配应用中，除以固定形式给出匹配的模式字符串外，大量的应用是以某种语法形式给出模式。例如，对于某种高级语言的编译程序来说，高级语言的语法公式就是一种模式，用这种高级语言编写的源程序是给定的正文。若源程序能被高级语言的语法公式匹配，则高级语言程序在句法上就是正确的，否则一定含有句法错误。 最简单的句法是一种称为正则表达式的句法。记有限的字符表为∑，∑上的字符正则表达式可递归定义如下： (1)空字符是∑上的正则表达式； (2)任何a∈∑，a是∑上的则表达式； (3)假定U和V都是∑上的正则表达式，那么，(U｜V)、(UV)和(U)*也都是∑上的正则表达式。 (4)仅由有限次使用上述三步骤而定义的表达式才是∑上的正则表达式。 在上述定义式的(3)中，（U|V）表示U或V的任选，（UV）表示U和V的连接，(U)*表示U的任意次（≥0）重复。 例如，令∑＝{a, b}，表7.2是∑上的正则表达式，以及正则表达式能匹配的正文集。 表7.2　字符正则表达式及对应的匹配正文集 由于正则表达式与有限自动机等价，正则表达式的识别可以直接从正则表达式自动构造相应的自动机，并由这个有限自动机识别输入正文是否能让指定的正则表达式匹配。这些知识属于编译技术的内容，这里不作进一步的讨论。以下用两个实例，采用动态规划法解决字符表达式的匹配问题。 正则表达式 能匹配的正文集 ab* ∑上所有以a为首字符，后接任意多个b的字符列 a(a|b)* ∑上所有以a为首字符的字符列 (a|b)*(aa|bb)(a|b)* ∑上所有含有两个相继的a或两个相继的b的字符列 【例7.1】判定一个字符表达式S能否匹配字符串T。 设字符表达式S除一般的普通字符外，还可以有两个特殊字符’+’和’？’。其中字符’+’能匹配任一字符列；字符’？’可以匹配任意一个字符；其它字符只能匹配相同的字符。另设被匹配的字符串T不包含字符’+’和字符’?’。 如字符表达式S为 +A?B+a 它能匹配字符串 abcAAxB12334a 但它不能匹配字符串 aabcAcxB1234a 设待匹配字符串T的长度为n(255)；字符表达式S的长度为m(255)。采用动态规划法，用一个两维数组a记录各子表达式匹配子字符串的情况。数组元素a[i][j]的意义如下： 1,