kmp(kmplayer plus安卓版)
KMP是什么啊
KMPlayer 是一款来自韩国的影音全能播放器, Kmplayer (简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展 KMP 可以支持层出不穷的新格式。强大的插件功能,直接从 Winamp 继承的插件功能,能够直接使用 winamp 的音频 ,输入,视觉效果插件,而通过独有的扩展能力,只要你喜欢,可以选择使用不同解码器对各种格式进行解码。内含中文语言包支持,不过界面汉化稍有欠缺。
第一 全能播放器所有格式的电影都可以看
第二 BT没有下载完的电影也可以看不管是99%或者多少都可以
第三 强大的面板可以每次使用的时候换颜色,让你眼前一亮焕然一新
第四 可以很便捷的通过键盘快捷建来调整如亮度 饱和度 对比度 3D环绕音等功能
第五 虽然是一款韩国的播放器,但是程序为多语言版本,内含简体中文
第六 占用系统资源极少 mpc 占用CPU40%, kmp 占用仅15%
第七 可自动切换播放文件(如 你的电脑种有一个名为"仙剑奇侠转"的文件夹里面是电视剧,你只要拖拽到播放器中第一个文件,即可在文件播放完毕后自动换到下一个文件),【注:文件的文件名必须顺次排序如 CD1 CD2。。。。等别的也可以】
第八 智能播放器,正在看电影的时候,要停下来下次再看得时候,播放器会帮你记住上次看到了哪里(这个功能菲利普DVD有哦)具体*作方法:播放中按暂停后关闭播放器即可,等下次观看时只要打开播放器后左键双击播放画面即可。
而且呢KMP比影音暴风更有用,可以调试画面色调和清晰度,KMP可以播放更多格式视频,比如BIK文件,影音暴风就不行!
我用的就是KMP 很好用的而且感觉外观要不暴风好看多了呢!呵呵
希望你有用 到讯雷里就可以直接下了 很快的!
kmp算法什么意思?
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下:
1) next[j] = -1 j = 0
2) next[j] = max(k): 0kj P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如:
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k0时,表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。
算法-KMP
大一下参加学校ACM预备队集训的时候首次接触KMP算法,当时看了很多介绍文章,仍然不是很理解其实质,只是简单地套模板AC题目,待大二数据结构与算法课堂上再听老师介绍一次,才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢?正巧最近和朋友聊天时他告诉我他对KMP不是很理解,于是打算自己写一篇文章,巩固自己对KMP的认识,也希望能够帮助更多朋友理解KMP。
在开始之前,需要知晓的概念:
前缀:以原串串头为自身串头的子串,如 的前缀有:
后缀:以原串串尾为自身串尾的子串,如 的后缀有:
注意:字符串前后缀都不包括该串本身
给你一个文本串T(Text String)
再给你一个模式串P(Pattern String)
问该模式串是否在文本串中,怎么找?
一开始只好分别从文本串与模式串的串头开始逐字母比较
二者相同,再比较T串与P串的下一位
如此反复
如果一直这么顺利,两串对应位置的字符总相同,待P串中最后一个字符也匹配完毕,说明该模式串在文本串中存在,耶( ?? ω ?? )y超开心,查找结束。但,大多数匹配过程不会如此顺利,在该例中,当匹配进行至
很明显,失配了。现在怎么办?按朴素思想,将P串相对T串整体右移一位,重新开始匹配,即
但这种算法效率无疑是十分低下的。设T串长度N,P串长度M,则朴素算法时间复杂度为O(MN)
已知的重要信息并没有被使用——已匹配的字符串前缀
在上例中,当P串最后一个字符匹配失败时,其已有包含七个字符的 前缀子串S 匹配成功
完全可以利用前缀子串S做点什么。观察到在S串
中,有相同前后缀,即下图蓝色部分
而S串各字符又与T串中对应字符相同,即有
当失配发生后,直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分
从图中红框部分继续尝试匹配,发现再次失配。这次,已匹配成功的前缀串S为
而在该串中没有相同的前后缀,只能将P串串头移至失配处进行比较
再次失配。此时前缀串S为空串,只好如朴素算法般将P串整体右移一位,重新开始比较
匹配成功。于是又按照之前的步骤往下匹配,直至再次失配或匹配成功
后续步骤同上,不再赘述
上述示例已展现,KMP算法的精髓在于对已匹配成功的前缀串S的利用
在朴素算法中,匹配失败了,T串待匹配字符会回溯
T串原本已匹配至T[7] = 'X',但是因为失配,需回溯到T[1] = 'b'重新开始匹配
而在KMP算法中,若P[M]与T[K]匹配失败,K不会回溯。既然匹配过程是从T[0]开始逐渐向右进行的,至T[K]失配发生时,T[0]至T[K-1]早已匹配过,何必再回溯过去重复匹配呢?于是乎,就如问题引入部分展示般
每当失配发生,我们总是去关注P串中已匹配成功的前缀串S
因为该前缀串是匹配成功的,说明在T串中必定存在与该前缀串相同的子串,记为S'
若S串中存在相同前后缀
则S'串必然也存在此相同前后缀
所以只需将P串右移四位,使得S串的该相同前缀对齐S'串的该相同后缀
再尝试比较T[7]与P[3]
至于T[7]与P[3]是否能够匹配另说(当然,本例中一看就知道没匹配上),但通过对前缀串S的利用,成功省去了P串右移一位、两位和三位后的无效匹配
继续深入思考,给定一个具体的P串,其第N位的前缀串S内容是固定的,则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之,对于一个具体的P串,当其与给定T串匹配至P[N]失配,P串应右移几位再次与T串进行匹配也是确定的。我们完全可以使用一个数组记录当P[N]失配后,应当使用N之前的哪一位再来与T串进行匹配,以此提高匹配效率,记该数组为Next数组
定义Next[i] = j表示当P串中第i位失配后,跳转至P串第j位再次尝试匹配
还是以之前的P串为例,它的Next数组求出来应为
取下标5为例,其前缀串为
最长相同前后缀为
若P[5]失配,应跳转至P[1]再次尝试匹配(最长相同前缀对应P[0],则取其后一位P[1],若存在多位,则取最后一位的下一位),P[5]的前一个字符P[4]对应字符'a',而P[1]前一个字符P[0]同对应字符'a',保证了P[1]之前字符与T串中对应字符保持匹配。所以Next[5] = 1,其余下标对应Next数组值同如此求。
特别地,规定Next[0] = -1。而对于除下标0外的任意下标N,Next[N]的含义是 前N-1个已匹配成功的字符构成的前缀串S中,最长相同前后缀长度。 所以若在下标为N处匹配失败了,则应前往Next[N]所对应的下标处匹配。
具体地,以下图所示为例,P[6]与T[6]失配
而Next[6] = 2,所以使用P[2]再次尝试与T[6]进行匹配
当求出P串Next数组后,便可快速进行与T串的匹配
现在问题只剩下如何求Next数组,注意到Next数组既然只与P串本身相关,与文本串T无关,故令P串与自身匹配即可求得
考虑字符串
其Next数组应为
令其与给定文本串相匹配
当匹配进行至
失配,于是跳转至P[Next[3]] = P[1]处再次尝试匹配
再度失配,也必然失配
问题在于不该出现P[N] =P[Next[N]]
若P[N] =P[Next[N]],则P[N]失配后使用P[Next[N]]再次尝试匹配,由于P[N] =P[Next[N]],P[N]匹配失败,P[Next[N]]必然也失败
因此,若出现P[N] =P[Next[N]]情况,则令Next[N]=Next[Next[N]]
本例中该字符串新Next数组为
当匹配进行至
失配,于是跳转至P[Next[3]] = P[0]处再次尝试匹配
省去了之前跳转至P[1]处的无效匹配
设T串长度M,P串长度N,由于KMP算法不会回溯,分析易知时间复杂度为O(m+n)
对于P[N],若其前缀串S含相同前后缀F,且F长度为n(n1),Next[N]可以取1至n中任意值,为最大化匹配效率考虑,总是取最大相同前后缀以提高效率,节省时间
KMP是什么意思
一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ,匹配时间为Θ(n),只用到辅助函数π[1,m],它是在Θ(m)时间内,根据模式预先计算出来的。数组π使得我们可以按需要,“现场”有效的计算(在平摊意义上来说)变迁函数δ。粗略地说,对任意状态q=0,1,…,m和任意字符a∈Σ,π[q]的值包含了与a无关但在计算δ(q,a)时需要的信息。由于数组π只有m个元素,而δ有Θ(m∣Σ∣)个值,所以通过预先计算π而不是δ,使得时间减少了一个Σ因子。