KMP next 数组讲解

Love The Way You Lie 2023-01-01 05:59 92阅读 0赞

### 文章目录 ###

*   *   *  KMP next 数组讲解
         *  C 语言版本代码：

### KMP next 数组讲解 ###

> 重点在于匹配不上回退的理解

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvdW5neW91dGg_size_16_color_FFFFFF_t_70_pic_center]

**最后粉色的讲解，笔者感觉是理解回退的关键。**

> 好像有点不清楚，上传的图片。

### C 语言版本代码： ###

> 吐槽几句：  
> 写吐了，代码就几句，写了好久，一直在百度C语法，C语言忘光了。  
>   
> Java写习惯了，感觉 C 是真的简陋啊，要啥，啥没有。  
>   
> 1 数组长度需要自己计算。  
>   
> 2 数组长度必须为常量，要实现 int a\[n\] 还要通过指针和malloc实现，然后实现出来的东西，还不能再求出它长度了，，，。  
>   
> 感觉像现代人回到了原始社会。。犹记当时大一会，我还是 C语言 课代表呢，C语言写的也是可以的啊，4,5年下来全还给老师了。

#include <stdio.h>
    #include <stdlib.h>
    
    #define ARRAY_LENGTH(x) (sizeof(x)/sizeof(x[0]))
    
    typedef struct { 
    	char data[50];
    	int length;
    }string;
    
    void GetNext(string pattern,int* next) { 
    	int j = 0; // 下标 从 0 开始。
    	int k = -1; // k 表示 最大公共前后缀长度，从 -1 开始 。
    	next[0] = k;
    
    	// 遍历 到 倒数第二位。因为每次遍历得到的值，是下一个下标的数组值。
    	// 下标0的数组值，在遍历之前就默认了。遍历第一轮是给下标1的数组单元赋值。
    	// 所以遍历到倒数第二位就好了。
    	while (j < pattern.length-1) {   
    		// k == -1 .既是为了设置 next[1] = 0 ; 
    		// 也是为了最后回退，一直不匹配，t[0]和t[j] 作比较
    		// 此时 k = 0 回退以后 k == -1 ，再次进入 if 条件设置 next[j] = 0 ;
    		if (-1 == k || pattern.data[k] == pattern.data[j]) { 
    			k++;
    			j++;
    			next[j] = k;
    		}
    		else { 
    			k = next[k];
    		}
    	}
    }
    
    void MyPrint(int array[],int length) { 
    	for (int i = 0; i < length;i++) { 
    		printf("%d ", array[i]);
    	}
    }
    
    int main() { 
    	char *temp = "aaababccacade";
    	string pattern;
    
    	for (int i = 0; '\0' != temp[i];i++) { 
    		pattern.data[i] = temp[i];
    		pattern.length = i+1;
    	}
    
    	int length = sizeof(int)*pattern.length;
    	int* const next = (int*)malloc(length);
    	GetNext(pattern,next);
    	MyPrint(next,pattern.length);
    
    
    
    	system("pause");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvdW5neW91dGg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/605bb5659c6d454aa81d68f9aa8c9324.png