Posted in 2010-01-24 2:27 PMJulius Chen
KMP算法是字符串匹配的一种改进算法，在1977年由D. E. Knuth，J. H. Morris和V. R. Pratt一起提出，并以他们名字的首字母命名。和朴素的模式匹配算法相比，KMP算法最大的特点就是主串指针不回溯。它利用已经得到的“部分匹配”信息来减少不必要的比较而加快字符串的匹配速度。
KMP算法的本质
KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建（或前缀函数的构建，KMP算法不用计算变迁函数，而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换），当完成有限自动机的构建之后对主串的搜寻就显得很简单了。
前缀函数next的构建
模式的前缀函数包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的模式匹配算法中对无用位移的测试。比如主串和模式串在主串指针为Ti、模式串指针为Pj处匹配失败时，可以主串指针不回溯并直接取next函数的值next[j] = k将模式串向右滑动到第k个字符处重新开始比较，而不用去做无用位移的测试。只是这样的操作能成立k必须要满足一定的条件，如下所示：
首先，如果模式串能直接向右滑动到第k个字符处重新开始比较则说明模式串中的前k-1个字符必然已经和主串匹配了，也即必然已经有下面式子，且为了能最大化的向右移动则不能存在更大的k’满足下面式子：
继续阅读 »
Posted in 2010-01-23 8:41 PMJulius Chen
朴素模式匹配算法又称简单匹配算法或Brute-Force算法，它是字符串模式匹配中比较简单的一种算法。它从主串的第一个字符开始进行模式匹配，依次比较主串和模式串中的每个字符，若比较全部相等（模式匹配成功），则返回模式串中第一个字符在主串中的位置，否则主串指针从比较失败的字符处回溯到第二个字符开始重新和模式串进行匹配，这样依此下去，直到和模式串匹配成功或到主串的末尾（匹配不成功）为止。
继续阅读 »
Posted in 2009-12-25 5:54 PMJulius Chen
基数排序和计数排序一样，是非基于比较的排序算法，它借助“分配”和“收集”两种操作对单逻辑关键字进行排序（基于箱/桶排序），它的排序速度很快，时间复杂度为线性，但由于需要的辅助空间太大（n(radix+1)），因此长期无法应用。直到1954年有人提出用“计数”代替“分配”才得以使它能在计算机上实现。此后，又有人提出用链表作为存储数据的结构，这样又能减少一些辅助空间，这也是一种比较好的实现方法（只是算法要较复杂）。
基数排序分为MSD（最高位优先）基数排序和LSD（最低位优先）基数排序，MSD从左到右处理关键字的位数，首先处理最重要的数字。它比较符合常规的思维，所需处理的信息量也较少。但按MSD进行排序，必须将序列逐层分割成若干个子序列，然后对各子序列分别进行排序；而LSD则从右到左先处理最不重要的数字，这样虽然可能花费了一些时间来处理不会影响结果的信息，但它不用分子序列，对每个关键字都是整个序列参加排序，而且对具体的应用还可以对其进行改进。因此在很多排序应用中都选择这种方法。
基数排序（LSD/用计数排序）的C/C++代码实现：
- void radix_sort(int a[], int length)
- {
- int i, j, digit;
- int c[16];
- int temp[ARRAY_SIZE];
- for (i = 0; i < HEX; ++i) {
- for (j = 0; j < 16; ++j) c[j] = 0;
- for (j = 0; j < length; ++j) c[a[j]>>4*i&0xf]++;
- for (j = 1; j < 16; ++j) c[j] += c[j-1];
- for (j = length - 1; j >= 0; --j) {
- digit = a[j] >> 4 * i & 0xf;
- temp[c[digit]-1] = a[j];
- c[digit]--;
- }
- for (j = 0; j < length; ++j) a[j] = temp[j];
- }
- }
继续阅读 »
Posted in 2009-12-24 6:34 PMJulius Chen
计数排序(Counting Sort)是一种非基于比较的排序方法，它要求所有的待排元素都必须是≥0的整数。它的排序步骤是首先根据数组中最大的元素值加1作为长度来定义一个计数数组C。然后统计待排数组中每个值为i的元素出现的次数，存入C的第i项中。再对所有的计数累加（从C中的第一项开始，每一项和前一项相加）。最后再反向填充辅助数组：将每个元素i放在辅助数组的第C(i)项，每放一个元素就将C(i)减去1。这样完成之后排序就已完毕，有序序列已存储在辅助数组中。如果结果想用原数组输出，则将它们从辅助数组考回到原数组即可。
计数排序的C/C++代码实现：
- void counting_sort(int a[], int length)
- {
- int i;
- int c[MAX_VALUE] = {0};
- int temp[ARRAY_SIZE] = {0};
- for (i = 0; i < length; ++i) c[a[i]]++;
- for (i = 1; i < MAX_VALUE; ++i) c[i] += c[i-1];
- for (i = length - 1; i >= 0; --i) {
- temp[c[a[i]]-1] = a[i];
- c[a[i]]--;
- }
- for (i = 0; i < length; ++i) a[i] = temp[i];
- }
继续阅读 »
Posted in 2009-12-22 6:27 PMJulius Chen
归并排序是建立在归并操作（Merging）上的一种排序方法，它是采用分治法的一个非常典型的应用。归并是指将两个或两个以上的有序表合并成一个新的更大的有序表，归并排序则是递归的先将待排序列分割成n个序列，然后从最小的有序序列（只含一个元素）开始不断调用归并操作进行合并直到最后都合并成一个大的完整的有序表为止。
归并排序的C/C++代码实现：
- void merge(int array[], int low, int m, int high)
- {
- int i, j, k;
- static int temp[ARRAY_SIZE];
- for (i = low, j = m + 1, k = 0; k < high - low + 1; ++k) {
- if (i > m) {
- temp[k] = array[j++];
- continue;
- }
- if (j > high) {
- temp[k] = array[i++];
- continue;
- }
- temp[k] = array[i] < array[j] ? array[i++] : array[j++];
- }
- for (k = 0; k < high - low + 1; ++k)
- array[low+k] = temp[k];
- }
-
- void merge_sort(int sort_array[], int low, int high)
- {
- if (low < high) {
- int i = (low + high) / 2;
- merge_sort(sort_array, low, i);
- merge_sort(sort_array, i + 1, high);
- merge(sort_array, low, i, high);
- }
- }
继续阅读 »
