算法分析一，字符串基础操作

"字符串基础操作和模式匹配算法" 字符串是计算机科学中最基本的数据结构之一，字符串基础操作是指对字符串进行赋值、复制、比较、连接、取子串、子串在主串中定位、子串置换、子串插入、子串删除等操作。 在字符串基础操作中，字符串模式匹配算法是指在文本（主串）中找出给定字符串（模式）的所有出现位置。字符串模式匹配算法可以分为两大类：基于是自动机或字符串组合特点的算法和对文本建立索引的算法。本节课只讨论第一类字符串模式匹配算法。 第一类算法是基于这样一种方式来进行的：设想一个长度为 m 的窗口。首先窗口的左端和文本的左端对齐，把窗口中的字符与模式字符进行比较，这称为一趟比较。当这一趟比较完全匹配或是出现失配时，将窗口向右移动。重复这个过程，直到窗口的右端到达文本右端。这 种方法我们通常叫 sliding window（窮舉法）。 对窮舉法来说，找到所有位置的匹配时间是 O(mn)。基于对窮舉法的改进结果，我们按照每一趟比较时的比较顺序，把算法分为以下四种：从左到右顺序、从右到左顺序、特殊顺序和任意顺序。 从左到右顺序模式匹配算法有 KR 算法、Shift-Or 算法、MP-KMP-Simon 算法等。KR 算法是最先由 Harrison 提出的，而后由 Karp 和 Rabin 全面分析，称为 KR 算法。Shift-Or 算法是在假设模式长度不大于机器字长时，Shift-Or 算法是很高效的匹配算法，同时它很容易扩展到模糊匹配上去。MP-KMP-Simon 算法是第一個線性時間複雜度的算法，随后被改进为 KMP 算法。 从右到左顺序算法有 BM 算法、Apostolico and Giancarlo 算法、Turbo BM 算法、Reverse Colussi 算法、Quick Search 算法、Reverse Factor 算法、Turbo Reverse Factor 算法、Zhu and Takaoka 算法、BR 算法等。BM 算法被认为是通常应用中最有效率的算法。 特殊顺序算法有 Galil-Seiferas 算法、Two Way 算法、Colussi 算法、Galil-Giancarlo 算法等。Galil-Seiferas 算法和 Two Way 算法把模式分为两部份，先从左到右搜索右边这部份，如果没有失配，再搜索左边这部分。Colussi 算法和 Galil-Giancarlo 算法把模式位置分为两个子集，先从左到右搜索第一个子集，如果没有失配，再搜索剩下的。 字符串基础操作和模式匹配算法是计算机科学中非常重要的两个概念，掌握这些概念对于开发高效的字符串处理算法非常重要。