欢迎您访问52IJ教育培训网，今天小编为你分享的高考语文方面的学习知识是通过网络精心收集整理的：“kmp算法_KMP算法简单易懂解释？或用一个简单例子逐步说明一下.谢![语文]”，注意：所整理内容不代表本站观点，如你有补充或疑问请在正文下方的评论处发表。下面是详细内容。
好吧~KMP当初我也想了挺久的~很巧妙的算法啊!相必复制百科什么的你也不会看的了所以我手打吧…下面是我的理解~
为了解说方便我把长的称为文本串,短的称为目标串~
常规的匹配算法是把目标串一位一位地右移,跟文本串比较,而KMP则是跳着右移~
举几个例子相信你就懂了
————————————————————————————————————————
比如有一目标串为ababaca,当前位置匹配了前5个,也就是匹配了ababa,后面两个不匹配
这说明了文本串当前位置也是ababa
显然右移一位是不行的,因为从目标串可以看出(abab)a与a(baba)括号里的内容不相等
而右移两位是可能可行的~因为可以看出(aba)ba与ab(aba)括号里的内容是相等的,这意味着移动两位后,目标串前三位aba是肯定匹配的~因为移动前也匹配~
————————————————————————————————————————
再举一个例子~比如有目标串abcab,当前位置匹配了前两个ab
那么就需要右移3个位置,因为(ab)cab与abc(ab)括号里内容相同,移动后有可能会匹配~
————————————————————————————————————————
懂了么?表达能力有限…我也不能讲得更好了…具体代码网上一大堆,《算法导论》里面也有~我当初就是在算导里学会的!
如果懂了,希望有追加分啊,手打累死!
不懂的话,追问吧……
其他类似问题
问题1：模式匹配KMP算法思想是理解的 但是对应的next分段函数 这是啥意思啊 这个函数的自变量和值 分别代表什么现实意义?
这时老问题了,我以前做过一个文章是理解KMP,你留一个邮箱,你看看,
算了我复制给你吧.
KMP算法一共分为两个部分,一个是失败函数,一个是快速查找函数(数据结构金远平版本),KMP难度不在两个分开的函数,而是如果大家要合起来看,那的确难以接受,所以,我是分开理解的.其中不乏很多小技巧,体现出程序的智慧.
首先,是失败函数.失败函数的目的要明确：就是求出对于每个元素之前的首尾与之对应的最大真子串的子串个数(1.之所以是真,也是为了保证不进入死循环；2.求出个数,也就是说失败函数是int型数组).那怎么求出每个元素的对应的最大子串树呢?
我们先来看看“人工”怎么求?例如：a b c a b c a c a b 那么,你就看看每个元素前面有没有与之匹配的元素,(我们将没有与之匹配的元素置为-1)最后发现
0 1 2 3 4 5 6 7 8 9
a b c a b c a c a b
-1 -1 -1 0 1 2 3 -1 0 1
那么我们人为理解了失败函数的功能,那么我们可以整理一下我们刚刚人工的思路：我们将当前元素与前面的元素比较?机器怎么做?存栈?impossible!那么机器理应看他前面那个元素的失败函数的值.那么好啦,如果只看前面函数的值,那我再前面的元素施加的影响怎么考虑进去,那就出现了技巧1,巧用c＋＋指针解决,我们用两个指针,一个指针做数组的全局扫面,一个指针做内部的调整(纪录我里面连续的字符串)（能不能只用一个指针?不可能!）.
那么我们来看看失败函数的算法
void String::Failed(){
int LengthP = Length;
f [ 0 ] = -1;//初始化第一个元素,一定找不到,为“－1”
for(int j = 0; j < LengthP; j ++){//一个指针j,一直++
int i = f [ j - 1 ];//一个指针i,不停做调整
while(*(str + j) != *(str + i + 1) && i >= 0)
i = f [ i ];//此处具体解释
if (*(str + j) == *(str + i + 1))
f [ j ] = i + 1;//依然匹配,直接＋＋
else
f [ j ] = -1;//没有匹配,－1
}
}
上面程序,最难懂的就是红色部分,道理何在?这里呢,不同的人有不同的说法,我仅以我的理解来讲,就是“匹配到死”!什么道理,就是说,一直找,找不到匹配就走人!比如以上面例子来说,如果遇到红色的c,那么根据我们刚刚分析的算法,先看他前面的元素,记下他失败函数的值（也就是i,i就是跟他匹配的最大字串的地址,这里为3）,那么*(str ＋ j)是c,那么*(str + i + 1)就是第4个元素为b,显然不匹配,那么下一步i ＝ ,i ＝ 0,到这里,或许你和我有一样的疑问?不成功那么按人脑应该想到是看看第一个元素?或是再看看前面几个元素与后面几个元素一样不一样?几个!别开玩笑了,计算机会杀了你,它只能看一个?那么看哪个?这里的技巧我实在是不能多说!太NB啦!他利用了失败函数的递归效应,运用其内部结构制约
这段太长,一定要分段啊.
也就是说,我第一个匹配的字符串是蓝色的b,那么不等,我下一次看的是谁?是b的最大子串的位置也就是绿色的b,那么好啦,这个例子还不能说明什么,
以下均为假设（也可以比如d c b d d c b d c）：如果我的红色正好和绿色相等,不是“好像”少看了一位,那就是,你怎么能保证绿色前面那位与我的红色前面一位相等?那么这里就是技巧2,因为我每次找都是找的子串,那么我一定能保证相等（也就是 红c前面的一定等于蓝d前面的d也等于绿c前面的d）.ok,到这里,不知大家的感觉是更清楚还是在心理狂骂我.
接下来就是较为简单的快速查找,利用了失败函数的快速查找,效率什么也自然就高了.以下是程序:
int String::FastFinding(String *pat){
int j = 0,i = 0;// 申请两个指针,分别扫描模版字符串和目标串
int LengthP = pat.Length,LengthS = Length;
while( j < LengthP && i < LengthS )
if( pat.str[ j ] == str[ i ])
i ++;
j ++;//相等,都好说
else
if(j == 0) i ++;// 不等,而且j刚好才扫到第一个
else j = pat.f[ j-1 ] + 1;//详细讲
if( j < LengthP || LengthP == 0) return -1;//没有找到
else return i - LengthP;//找到了
}
这段代码的难点也是红色子部分,这部分是说没有匹配,那么模版串要怎么移动,熟悉“蛮力匹配”算法的都清楚,他要回朔,就是模版串要走回头路,那么我KMP算法就是要尽量少走回头路,你可以把问题相成两把尺子,一把大尺子和一把小尺子,那么蛮力匹配就是每次小尺子只移动一格,每次i＋＋,那么KMP是每次平均可以移动很多格（最好是没有匹配的,也就是j ＝ 0,那么每次都是大踏步前进!）（这里要大家理解了,这个是动态图,我懒的做了）所以他好!
其余,KMP的时间复杂度,正确性我就不多谈了,这些我们不care!
那么到这里,KMP算法也算是讲完了,我觉得又理解了一遍,不错不错!
你要电子版就留邮箱
问题2：如何理解KMP法已知主串S='acabaabaabcacabc'模式串P='abaabcac'给出KMP法进行模式匹配的各趟匹配结果[数学科目]
首先next是干什么的.next[i]是指在（这里的i是1-n的）第i个匹配失败时,跳到前面的第几个字母.0就是跳过自身继续.
P= abaabcac
next 01122312
nextval 01021302
首先
acabaabaabcacabc
abaabcac
卡在2位上了
next[2]=1('b')
acabaabaabcacabc
abaabcac
卡1位,0,直接跳
acabaabaabcacabc
abaabcac
卡6位c,3,回到ab(a)xx
那么就是
acabaabaabcacabc
abaabcac
然后就匹配上了.
问题3：有哪些说明方法（举例）…………~[语文科目]
常见的说明方法有举例子、引资料（引用）、分类别、列数字、作比较、画图表、下定义、作诠释、打比方、摹状貌、作假设这11种.小学常见的有：举例子、列数字、打比方、分类别、作比较.中学常见的有：举例子、列数字、打比方、分类别、作比较、作引用、画图表、下定义、作诠释、摹状貌.“摹状貌”和“作假设”小学和初中不常用,一般是到高中和大学才可能学到.
（1）举例子
举出实际事例来说明事物,使所要说明的事物具体化,以便读者理解,这种说明方法叫举例子.好处：使文章表达的意思更明确,更生动形象,读者更明白,增强说服力.
（2）引资料（引用）
为了使说明的内容更充实具体,可以引用一些文献资料、诗词、俗语、名人名言等,可使说明更具说服力.好处：使文章更具说服力.体现说明文语言的准确性.引用古诗：使说明文更具诗情画意
（3）作比较
作比较是将两种类别相同或不同的事物、现象加以比较来说明事物特征的说明方法 好处：说明某些抽象的或者是人们比较陌生的事物,可以用具体的或者大家已经熟悉的事物和它比较,使读者通过比较得到具体而鲜明的印象.
（4）列数字（列数据）
为了使所要说明的事物具体化,还可以采用列数字的方法,以便读者理解.需要注意的是,引用的数字,一定要准确无误.好处：数字是从数量上说明事物特征或事理的最精确、最科学、最有说服力的依据.（用列数字的方法进行说明,既能准确客观的反映事实情况,又有较强的说服力.）
（5）分类别
要说明事物的特征,往往从单方面不易说清楚,可以根据形状、性质、成因、功用等属性的异同,把事物分成若干类,然后依照类别逐一加以说明.这种说明方法,叫分类别.好处：条理清晰,一目了然.
（6）打比方
利用两种不同事物之间的相似之处作比较,以突出事物的性状特点,增强说明的形象性和生动性的说明方法叫做打比方.好处：抽象的事理变得具体、生动、形象.（或把事物的特征解说得确切具体、浅显易懂.）
（7）摹状貌
为了使被说明对象更形象、具体,可以进行状貌摹写,这种说明方法叫摹（mó）状貌.好处：使被说明对象更形象、具体.
（8）下定义
用简明的语言对某一概念的本质特征作规定性的说明叫下定义.下定义能准确揭示事物的本质.好处：使人们在阅读时对抽象的字词能够更加明白、理解.
（9）作诠释
从一个侧面,在事物的某一个特点做些解释,这种方法叫作诠释.好处：使读者在阅读时对抽象的字词能够更加理解.
（10）画图表
为了把复杂的事物说清楚,还可以采用图表法,来弥补单用文字表达的缺欠,对某些事物解说更直接、更具体.好处：使人看了一目了然.
问题4：kuhn-munkres算法是怎样的?最好的简单易懂的讲解,有例子最好![数学科目]
自己查!
问题5：kmp 算法原理
朴素算法
先看看最“朴素”的算法： ///find a template in a string. #include #include int Index(char *S, char *T, int pos) { int k=pos, j=0; while(k 0 and P[q+1]≠T[i] 7 do q ← π[q] △Next character does not match. 8 if P[q+1]=T[i] 9 then q ← q+1 △Next character matches. 10 if q=m △Is all of P matched? 11 then print “Pattern occurs with shift” i-m 12 q ← π[q] △Look for the next match. COMPUTE-PERFIX-FUNCTION(P) 1 m ← length[P] 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k>0 and P[k+1]≠P[q] 6 do k ← π[k] 7 if P[k+1]=P[q] 8 then k ← k+1 9 π[q] ← k 10 return π[1]
编辑本段KMP算法的c++实现
//c++实现的KMP算法,所有涉及字符串,其初始下标从0开始(上述算法均是从1开始) //example: char s[100],t[100];cin>>s>>t;KMP(s,t); //获取待查询模式的next数组 int* get_next(char* T, int* next){ int i = 0, j = -1; int length = strlen(T); int *temp = next; *next = -1; while(i< length){ if(j==-1 || *(T+i)==*(T+j)){ i++; j++; //优化后的get_next方法,可以防止出现形如"aaaaab"这种模式的计算退化 if(*(T+i)!=*(T+j)) *(next+i)=j; else *(next+i)=*(next+j); } else j=*(next+j); } return temp; } //KMP算法 int KMP(char *S, char *T){ int S_Length = strlen(S); int T_Length = strlen(T); //若模式长度大于字符串,则直接返回查询失败 if( S_Length < T_Length) return 0; int i = 0, j = 0; int* next = new int[T_Length]; get_next(T, next); while(i < S_Length && j < T_Length){ if(j == -1 || *(S+i) == *(T+j)){ i++; j++; } else j=*(next+j); } if(j>=T_Length) return i-T_Length; return 0; } 在此提供一个更简明的适用于字符串的kmp实现： #include #include int next[100]; void getnext(char b[]) { int i=1,j=0; //i是每个位子,j是回退的位子 next[1]=0; while(i
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-