论文部分内容阅读
字符串查找是计算机科学中基础的问题，涉及到文本编辑、数据检索、符号操作、搜索引擎等。算法复杂度是衡量算法运行效率的一把尺子，对算法的复杂度的分析是研究算法的重要课题。本文利用了马尔科夫链理论对经典字符串搜索算法KMP算法和初等算法的复杂度做了精确的刻画。文章安排如下：1．第一章主要介绍了字符串匹配算法和算法复杂度的一些知识。2．第二章描述了KMP算法和初等算法。3．第三章对我们要使用的工具马尔科夫链理论做了相关的说明。4．第四章给出了分析的过程和得到的主要结果。