字符串匹配的应用范围非常广泛,包括文档编辑、入侵检测、病毒特征码查找、防火墙技术、基因序列匹配等多个领域。Sunday算法是当前应用广泛并且比较高效的单模式匹配算法。但是当模式串和文本串均存在大量的重复字符时,Sunday算法的匹配次数将随着首字符的重复次数快速增加,在这种情况下,算法的执行效率将大大低于KMP算法。为了扩大Sunday算法的适用范围,提高其平均执行效率。本文提出了一种基于Sunday算法的改进算法,在算法匹配工作开始前进行预处理,将重复的首字符压缩为一个字符,然后使用压缩后的字符串和正文进行匹配,如果匹配成功,返回成功匹配的位置信息,然后开始进行回溯,即对成功匹配的位置信息前的字符和首字符进行循环匹配,如果匹配位数和模式串相同,则返回成功,否则返回失败。可以减少大量无意义的匹配次数,提高算法的执行速度。最后,分析改进后算法的性能,并通过实验进一步证明了改进算法的有效性。由于直接对字符串匹配算法构造状态转化图进行效率分析时的计算过程过于复杂。本文提出了一种以穷举算法为基准,根据算法匹配差值计算算法效率的方法,并以Sunday算法为例进行了效率分析。因为Barth对穷举算法的估计结果偏差较大,但穷举算法起着非常重要的基准作用。因此首先对穷举算法进行效率分析。在对穷举算法的匹配过程进行了详细分析的基础上,构建马尔可夫链的状态转换图描述其匹配过程,并对状态转换图进行简化。最终的状态图没有吸收态,且当n较大时每个状态的转换概率都会收敛为一个稳定值。根据以上特点可求得每个状态的转换概率,得到穷举算法比较精确的平均效率估计公式。其次,Sunday算法是最新的对BM算法进行了大幅改进的算法,和BM算法相比效率有了较大的提高,在实践中得到了广泛使用,具有新颖性和代表性。因此选择Sunday算法进行效率分析。对Sunday算法的匹配过程比较复杂、使用坏字符启发跳转、难以构建马尔可夫链的特点,采用间接的方法得到算法效率。即在得到穷举算法精确的匹配效率后,对Sunday算法和穷举算法的匹配过程进行详细的分析,得出两者的区别。将两种算法按照模式串尾字符所对应文本字符的下一个字符是否属于模式串分类讨论,通过概率论相关知识计算出Sunday算法和穷举算法平均匹配次数的差值。最后将穷举算法的匹配效率与两种算法的差值相减,得出Sunday算法平均效率估计公式。为使实验文本串的大小和字母表容量严格相同,并在最差情况下匹配成功。我们将文本串的字符随机交换位置后形成新的文本,将新文本和模式串进行匹配。如此不断循环,直到不产生新的匹配次数。最后删去匹配次数相同和不在最差情况下匹配的文本串。实验结果表明,由理论计算的估计值确实是算法实际匹配次数的平均值。