模式匹配KMP算法思想是理解的 但是对应的next分段函数 这是啥意思啊 这个函数的自变量和值 分别代表什么现实意义?

模式匹配KMP算法思想是理解的 但是对应的next分段函数 这是啥意思啊 这个函数的自变量和值 分别代表什么现实意义?
模式匹配KMP算法思想是理解的 但是对应的next分段函数 这是啥意思啊 这个函数的自变量和值 分别代表什么现实意义?

模式匹配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算法也算是讲完了,我觉得又理解了一遍,不错不错!
你要电子版就留邮箱