数据结构与算法第三章共88页资料.ppt

朴素匹配算法 效率分 析 ? 假定目标 T 的长度为 n 模式 P 长度为 m 且 m n ? 在最坏的情况下每一次循环都不成功则 一共要进行比较 n-m+1 次 ? 每一次相同匹配比较所耗费的时间是 P 和 T 逐个字符比较的时间最坏情况下共 m 次 ? 因此整个算法的最坏时间开销估计为 O(mn) 朴素匹配算法 最差情况 ? 模式与目标的每一个长度为 m 的子串进行比较 ? 目标形如 a n