KMP算法求next数组的问题-鞋百科

今天鞋百科给各位分享kmp的next怎么算的知识，其中也会对KMP算法求next数组的问题进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在我们开始吧！

KMP算法求next数组的问题

字符串如果是以0为下标的话next[7]是0，只有最后一位与第一位相等。

在第i个字符前面的i-1个字符里面，

KMP算法求next数组的问题

从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0；

从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1；

从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2；

前缀next数组的求解算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字符串长度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推。

扩展资料：

kmp算法完成的任务是：给定两个字符串O和f，长度分别为n和m，判断f是否在O中出现，如果出现则返回出现的位置。常规方法是遍历a的每一个位置，然后从该位置开始和b进行匹配，但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)。

参考资料来源：百度百科-简约KMP算法

KMP算法中的next数组值的疑问

问题1数组下标是从1开始计算问题2数组下标从0开始

看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算法也算是讲完了，我觉得又理解了一遍，不错不错！
你要电子版就留邮箱

给出字符串在KMP算法中的Next数组

逐个查找对称串。

只要循环遍历这个子串，分别看前1个字符，前2个字符，3个... i个最后到15个。

第1个a无对称，所以对称程度0

前两个ag无对称，所以也是0

依次类推前面0-4都一样是0

最后一个是0～3都一样是0

前缀next数组的求解算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字符串长度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推

while( Pattern[i] != Pattern[k] && k!=0 )

k=prefix[k-1]; //继续递归

if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

}

扩展资料：

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用**算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

参考资料来源：百度百科-kmp算法

KMP算法中的next数组如何计算

next[i]表示的是：
在第i个字符前面的i-1个字符里面，
从开头开始的1个字符与最后1个字符是否相等，若不是，则next[i]=0,否则继续看下面；
从开头开始的2个字符与最后2个字符是否相等，若不是，则next[i]=1,否则继续看下面；
从开头开始的3个字符与最后3个字符是否相等，若不是，则next[i]=2,否则继续看下面；
……
就是这样的判断取值。
它的意思就是如果到了某个字符不匹配的情况时候，你就可以直接把模式串拖到从开头开始的那next[i]个字符等于当前字符的前next[i]个字符的地方，这样就少了很多重复的无效的比较和移动。

数据结构KMP模式匹配算法的next[j]为什么是下面写的那样

你的理解有点偏差，设模式串为string[i],求next[j]不是前面一个相等就加一，而是要看前面紧接的子串有多少个相等，j=4时紧接的子串只有string[3]==string[1],故next[j] =2，同理j=5时也只有string[4]==string[1]，故next[j] =2。如果要next[5]=3,必须要满足string[3]==string[1]并且string[4]==string[2]的条件。

你看的是不是清华大学那本数据结构呢，有点说的不清不楚的。那个求next数组的算法多看几遍就可明白了。

KMP算法 next()函数 next[j]=0 当j=1时?

如果是next【j】=1的话，根据模式匹配又会回到第一个进行比较，这没有意义啊。。陷入循环啊！。。所以next【j】相当于一个标记，便于判断比较的

关于KMP算法，next第一个值到底是什么？！

上代码,有详细说明

public class KMP {

String model = "abcdabce";

String model = "abcabcabd";

String model = "aaaab";

String model = "asdaaaaaaabdabcabcaabaaaaaskdf";

char[] tempModel = model.toCharArray();

String str = "asdaaaaaaabdabcabcaabaaaaaskdf";

char[] tempStr = str.toCharArray();

int[] backto = new int[model.length()];

int[] next = new int[model.length()];

//查找用例

public void findStr(){

int i=0;

int j=0;

while(i<tempStr.length){

if(tempStr[i] == tempModel[j]){

i++;

j++;

}else{

j = backto[j];

if(j<0){

i++;

j++;

}

if(j == tempModel.length){

System.out.println(i+" "+tempStr[i-1]);

j=0;

}

鞋百科推荐内容：

请教：有一种柳叶形的钻头，扁的，谁知道是什么钻头？谢谢先！

2021年送外卖选择哪个平台好？美团众包、蜂鸟众包、点我达、达达骑手哪个好？

主角叫徐少杰的小说？

办理工行的VIP卡，需要什么条件

/**

* a a a a b

* -1 -1 -1 -1 3

* a b c d a b c e

* -1 0 0 0 -1 0 0 3

public void next(){

int i=0, //模式串下标,即当前位置.开始为0

k=-1;//k表示字符串在位置i之前已匹配的子串最长长度.类似于模式串的下标(从0开始)

next[i]=-1;//第一个next为-1

while(i+1<tempModel.length){//i 模式串的当前位置,因为第一个next为-1,所以从第二个开始,往前查找模式长度

if(k == -1 //初始,k,i直接自加:k=0,i=1

tempModel[k] == tempModel[i]){//比较第k个字符和第i个字符

i++;

k++;

if(tempModel[k] != tempModel[i]){//比较第k+1个字符和第i+1个字符不相等,说明k为当前模式最长长度.

next[i] = k;//k最小为0,因为i是从第二个开始的

}else{//第k+1个字符和第i+1个字符相等,说明第i+1个字符比较不同后,可后推到第next[k]个字符开始比较

next[i] = next[k];

}

}else{//往后找k值,此时k值表现为模式串的下标

k = next[k];

}

public void start(){

System.out.println("--------------------------------");

next();

//CommonUtil.printCharAndIntArray(tempModel,next);

}

public static void main(String[] args){

new KMP().start();

}