数据结构字符串模式匹配中计算next和nextval的值（C语言）

r囧r小猫 2023-06-10 06:28 6阅读 0赞

### 在KMP模式匹配中通过next的值可以快速达到匹配目的，那next的值怎么计算呢？ ###

### 其实计算next的值本身也就是对模式串进行模式匹配，我们一起看看计算next的值的过程； ###

### 当模式串 P=“ababcabaababb” 时计算它的next值。 ###

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70][] #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 1][]

###  比如： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 4][]

### 代码： ###

void get_next(m_1 A)
    {
    	int i=-1,j=0;
    	A->next[0]=-1;   //next[0]为-1，你们可以默认加一，原因我在下面解释
    	while(j<strlen(A->mel))   
    	{
    		if(i==-1 || A->mel[i]==A->mel[j])  //当i=-1(默认加一)或前缀子串和后缀字串等于
    		{
    			i++;
    			j++;
    			A->next[j]=i;
    		}
    		else i=A->next[i];
    	}
    	
    }

### i从-1开始的原因： ###

### 有些书为了方便理解把模式串的第一个字串的下标设为1，但事实上字符串的第一个字符下标为0 ###

![20191026123301861.png][]

### 完整代码： ###

#include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define MAXSIZE 100
    typedef struct N{
    	char hel[MAXSIZE];
    	int hel_size;
    }*n_1,n_2; 
    typedef struct M{
    	char mel[MAXSIZE];
    	int mel_size;
    	int next[MAXSIZE];
    	int nextval[MAXSIZE];
    }*m_1,m_2;
    
    void get_next(m_1 A);
    void get_nextval(m_1 A);
    void print(m_1 A);
    m_1 create_n_m();
    main()
    {
    	m_1 A=create_n_m();
    	scanf("%s",A->mel);
    	printf("%s %d\n",A->mel,strlen(A->mel)); 
    	get_next(A);
    	get_nextval(A);
    	print(A);
    }
    
    m_1 create_n_m()
    {
    	m_1 P=(m_1)malloc(sizeof(m_1));
    //	n_1 Q=(n_1)malloc(sizeof(n_1));
    	return P; 
    }
    
    void get_next(m_1 A)
    {
    	int i=-1,j=0;
    	A->next[0]=-1;   //next[0]为-1，你们可以默认加一，原因我在下面解释
    	while(j<strlen(A->mel))   
    	{
    		if(i==-1 || A->mel[i]==A->mel[j])  
    		{
    			i++;
    			j++;
    			A->next[j]=i;
    		}
    		else i=A->next[i];
    	}
    	
    }
    
    void get_nextval(m_1 A)
    {
    	int j=1;
    	A->nextval[0]=-1;
    	while(j<strlen(A->mel))
    	{
    		if(A->mel[j]==A->mel[A->next[j]])
    		{
    			A->nextval[j]= A->nextval[A->next[j]];
    		}
    		else
    		A->nextval[j] = A->next[j];
    		j++;
    	}
    }
    //ababcababaababb
    //ababcabaababb
    
    void print(m_1 A)
    {
    	int i;
    	printf("\n"); 
    	for(i=0;i<strlen(A->mel);i++)
    	printf("%c  ",A->mel[i]);
    	printf("\n");
    	for(i=0;i<strlen(A->mel);i++)
    	printf("%d  ",A->next[i]+1);
    	printf("\n");
    	for(i=0;i<strlen(A->mel);i++)
    	printf("%d  ",A->nextval[i]+1);
    }

计算nextval，每一次比较时，当前位的字符和当前位置的字符的next值对应的字符进行比较，由于时间原因在这里我就不解释了，如果不懂私聊我或者在评论区提问，我会尽量解释清楚。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70]: /images/20230531/e1d883ad8abc466da61e58ff3d2d0e93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 1]: /images/20230531/992cac8ad2e4412bbd439619dbdfb720.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 2]: /images/20230531/4e9dcc1bc6a84aedb61c1ccb61221aac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 3]: /images/20230531/976bae3912bc4e10aa8fe76c3222b640.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70 4]: /images/20230531/5a8d22a8ceda4c1e8969ba3a01d67b47.png
[20191026123301861.png]: /images/20230531/f5a81e44f46e457ea3cd29d862df161c.png