| 共 42 篇文章 |
|
若对于关键字集合中的任一个关键字，哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址“，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。（1）直接定址法 取关键字或关键字的某个线性函数值为哈希地址。给定的K值，... 阅104 转0 评0 公众公开 14-09-20 11:15 |
阅136 转2 评0 公众公开 14-09-11 17:48 |
字符串匹配算法比较 字符串匹配（string match)是在实际工程中经常会碰到的问题，通常其输入是原字符串(String)和子串（又称模式，Pattern)组成，输出为子串在原字符串中的首次出现的位置。通常精确的字符串搜索算法包括暴力搜索(Brute force)，KMP, BM(Boyer Moore), sunday, robin-karp 以及 bitap。KMP是经典的字符串匹配算法。Boyer Moore... 阅175 转1 评0 公众公开 14-08-31 23:32 |
如下图所示如果设当前节点的父亲节点的后缀节点为w，我们假设w具有c孩子为，我们可以看到对于w的整个c子树来说，因为根本不存在通向它们的边c，它们也就不可能是不良字符串，这样这些节点的危险性也就等价与它们的后缀节点的危险性了，而它们的后缀节点，实际上就是w的后缀节点的c孩子，如此回溯下去，最后就能找到。（3）其余节点的后缀节点，... 阅105 转0 评0 公众公开 14-08-31 23:30 |
字符串匹配算法。一 精确字符串匹配 字符串的精确匹配算法中，最著名的有KMP算法和BM算法。1：KMP算法KMP算法，即Knuth-Morris-Pratt算法，是一种典型的基于前缀的搜索的字符串匹配算法。所以过滤算法的思路为：通过过滤算法过滤文本中不能产生成功匹配的区域，然后结合非过滤文本搜索算法，最终实现快速字符串匹配。文本过滤算法则通过... 阅270 转0 评0 公众公开 14-08-31 23:28 |
这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force算法，然后就介绍了KMP算法。-：Sunday算法。Sunday算法其实思想跟BM算法很相似，只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。时间复杂度是O(mn)// 下面是Microsoft的实现//经典算法//比KMP算法简单,没有KMP算法高效char *... 阅38 转0 评0 公众公开 14-08-31 23:27 |
而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。上式的意义是，对于某个阶段k的某个状态xk，从该阶段k到最终目标阶段n的最优指标函数值等于从xk出发取遍所有能策略pkn所得到的最优指标值中最优的一个。使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*={u... 阅210 转2 评0 公众公开 14-06-25 20:14 |
五大常用算法之四：回溯法 1、概念。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（3）递归的算法框架。回溯法是对解空间的深度优先搜索，在一般... 阅38 转0 评0 公众公开 14-06-25 20:02 |
递归常常用于分治算法、动态规划算法中。同时，它又与递归法类似，当问题不能分解为独立的阶段，却又符合最优化原理时，就可以使用动态规划法，通过递归决策过程，逐步找出子问题的最优解，从而决策出问题的解。二、算法策略间的关系 1、对问题进行分解的算法策略——分治法与动态规划法。动态规划法 = 分治算法思想 + 解决子问题间的冗余情况 ... 阅200 转3 评0 公众公开 14-06-25 20:01 |
五大常用算法之五：分支限界法。所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展... 阅49 转0 评0 公众公开 14-06-25 20:00 |
