category·Algorithm

KMP算法 at: 2016-12-10
在字符串匹配算法里面有一种算法叫kmp算法。其实这种算法原理很简单，用模式串的前缀和后缀性质减少比较次数，从而达到提高效率的目的。假如在字符串 T = {a,b,c,d,e,a,b,c,d,a,b,d} 中搜索字符串 P = {a,b,c,d,a,b,d}，则字符串 P 成为模式串。 其实KMP算法建立在 3 条引理之上的。见算法导论（p591）。

深度优先遍历 at: 2016-12-09
本文介绍了一下深度优先遍历（depth-first search，DFS）的框架。下面代码使用了 vector 式的邻接表，其中 G[u][i] 表示结点 u 的第 i 个子结点。每条边用（u，v）表示。 12345678910111213141516171819#include <stdio.h>int maxn=100;std::vec..

大数问题 at: 2016-12-07
昨天瞌睡状态下写了一下大数相乘，各种低级bug，类型转换、参数写错、少写语句。。刚刚又写了一下。直接贴代码吧，写出来之后去poj2389跑了下过了。不过我发现，如果声明数组的时候size是变量（char c[clen]），在oj上会编译出错啊。但是sublime下没有这个问题。 123456789101112131415161718192021222..

链表的常见操作 at: 2016-12-05
链表的常见操作，摘自《剑指offer》。 0 链表的增加和删除操作。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455//LinkedListstruct ListNode{ int m_n..

散列表 at: 2016-11-28
定义维基百科定义：[ 散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表 ] 一句话说：散列的实质就是在元素的存储位置和它的关键码（key）之间建立一种..

贪心算法设计 at: 2016-11-28
几个简单问题： 区间选点问题首先将b升序排列，选b[0]作为第一个选点，当a[i]>b[0]的时候，b[i]作为第二个选点；以此迭代。

poj1159 at: 2016-11-27
题目：Palindrome. A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given..

递归与分治 at: 2016-11-27
综述递归是一种思想，分治是一种算法。分治算法的思想是将一个较大的问题分解为若干个与原问题相似的小问题进行求解。分治算法可以用递归或者迭代的思想实现。分治法的一般步骤如下： 划分, 把问题分解为若干子问题 求解，递归求解子问题 合并，把子问题的解合并为原问题的解 经典问题可以采用分治法的问题有： 棋盘覆盖问题 在一个已排序数组中找到对应的元..

并查集 at: 2016-11-23
假设第i条边的两个端点序号和权值分别保存在u[i],v[i],w[i]中，排序后第i小的边的序号保存在r[i]中。 1234567891011121314151617int cmp(const int i, const int j) {return w[i]<w[j];}int find(int x) { retur..