常用算法总结

桃扇骨 2022-08-07 15:34 152阅读 0赞

--------------------

# [KMP算法][KMP] #

## 简介 ##

kmp算法又称“看毛片”算法，是一个效率非常高的字符串匹配算法。  
kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。

## kmp算法思想 ##

在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。我们可以得到如下的结论：  
A段字符串是f的一个前缀。  
B段字符串是f的一个后缀。  
A段字符串和B段字符串相等。

--------------------

# [分治算法][Link 1] #

## 简介 ##

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

--------------------

# [动态规划][Link 2] #

## 简介 ##

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

能采用动态规划求解的问题的一般要具有3个性质：

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

f(n,m)=max\{f(n-1,m), f(n-1,m-w\[n\])+P(n,m)\}

--------------------

4.

--------------------

[KMP]: http://blog.csdn.net/yutianzuijin/article/details/11954939
[Link 1]: http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html
[Link 2]: http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关常用查找算法总结

一、顺序查找　　条件：无序或有序队列。　　原理：按顺序比较每个元素，直到找到关键字为止。　　时间复杂度：O(n) 二、二分查找（折半查找）　　

爱被打了一巴掌/ 2022年10月29日 11:21/ 0 赞/ 166 阅读

相关常用排序算法总结

目录比较排序插入排序 O() 冒泡排序 O() 快速排序O(nlgn) 归并排序O(nlgn) 线性时间排序计数排序O(n+k) 基数排序O(pn+pk)

Myth丶恋晨/ 2022年10月29日 07:41/ 0 赞/ 265 阅读

相关常用解题算法总结

一、四大基本算法分治法动态规划（一次买卖股票、多次买卖股票、最大连续子序列和、最大连续子序列积、最长公共子序列）贪心算法穷举法二、常用便捷算法异或法（单

朴灿烈づ我的快乐病毒、/ 2022年10月06日 06:49/ 0 赞/ 140 阅读

相关常用排序算法总结

> 总结来自《数据结构与算法应用实践教程》主编李文书一、稳定性关键字值相同的数据经过排序后相对次序保持不变二、分类总结 1. 插入排序：直接插入排序，

ゞ浴缸里的玫瑰/ 2022年08月22日 00:08/ 0 赞/ 217 阅读

相关常用算法总结

-------------------- [KMP算法][KMP] 简介 kmp算法又称“看毛片”算法，是一个效率非常高的字符串匹配算法。 kmp算法完成的任

桃扇骨/ 2022年08月07日 15:34/ 0 赞/ 153 阅读

相关常用排序算法总结

相关资料 1. [常用排序算法比较及具体代码实现][Link 1] 2. [各种排序算法详细说明(wiki)][wiki] --------------------

本是古典何须时尚/ 2022年08月07日 11:39/ 0 赞/ 160 阅读

相关常用查找算法总结

本文主要介绍四种常用的查找算法，即顺序查找，二分查找，哈希表查找和二叉排序树查找 1.顺序查找顺序查找是在一个已知无(或有序）序队列中找出与给定关键字相同的数的具

不念不忘少年蓝@/ 2022年07月26日 08:47/ 0 赞/ 150 阅读

相关常用排序算法详细总结

排序算法总结 ![70][] [常用排序算法(一) 插入排序、希尔排序、冒泡排序][Link 1] [常用排序算法(二) 选择排序、快速排序][Link 2]

ゝ一世哀愁。/ 2022年05月16日 04:48/ 0 赞/ 177 阅读

相关常用排序算法总结

前言: 最近在编程的时候总是遇到关于数组排序的问题,所以就想写一篇博客来总结几种常用的排序方法.我们下面所列举的排序都是升序排序,主要讲述的是算法,降序排序类似. 常

小咪咪/ 2022年04月01日 03:22/ 0 赞/ 285 阅读

相关常用排序算法总结

常用排序算法总结：选择法、冒泡法、直接插入法、希尔算法、快速算法、归并算法 2019年04月08日 10:52:26 [意义丶][Link 1] 阅读数：1622 本文

不念不忘少年蓝@/ 2022年02月02日 05:01/ 0 赞/ 217 阅读