KMP 模式匹配算法（C语言版）

逃离我推掉我的手 2024-02-23 08:12 61阅读 0赞

## 一、KMP算法的工作原理 ##

在我们进行字符串的模式匹配操作时，常用的算法有BF模式匹配算法和KMP模式匹配算法，其中BF模式匹配算法也就是常见的暴力解法，其时间复杂为O（m\*n），而KMP算法时间复杂m+n）其优化了BF模式匹配算法中的指针回溯问题，算法效率大大提高。

具体是（串从一开始计数）：

1、在匹配过程中，目标串的指针不需要回溯，只回溯模式串的指针。

2、如果目标串和和模式串前n个字符匹配成功，遇到匹配失败的字符时，模式串指针回溯的位置有模式串的内容决定（回溯到 匹配失败位置前的模式串的最长公共前后缀的长度加一的位置）。然后继续比较。

## 二、KMP算法的工作思想 ##

图解为一个典型的KMP算法步骤。![feefc3520ea24173b1806ed75ef20496.png][]

首先要计算模式串的next数组，即为模式串对应下标的回溯位置（下标从0开始）。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>位置</td> 
   <td>前置串</td> 
   <td>公共前后缀</td> 
   <td>位置</td> 
  </tr> 
  <tr> 
   <td>0</td> 
   <td>NULL</td> 
   <td>无</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>A</td> 
   <td>无</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>AB</td> 
   <td>无</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>ABA</td> 
   <td>A</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>ABAA</td> 
   <td>A</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>ABAAB</td> 
   <td>AB</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>ABAABA</td> 
   <td>ABA</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

以下再举例说明当模式串下标从一开始的计算（ABAABAC）

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>位置</td> 
   <td>前置串</td> 
   <td>公共前后缀</td> 
   <td>位置</td> 
  </tr> 
  <tr> 
   <td>1（定值）</td> 
   <td>NULL</td> 
   <td>无</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2（定值）</td> 
   <td>A</td> 
   <td>无</td> 
   <td>1=0+1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>AB</td> 
   <td>无</td> 
   <td>1=0+1</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>ABA</td> 
   <td>A</td> 
   <td>2=1+1</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>ABAA</td> 
   <td>A</td> 
   <td>2=1+1</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>ABAAB</td> 
   <td>AB</td> 
   <td>3=2+1</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>ABAABA</td> 
   <td>ABA</td> 
   <td>4=3+1</td> 
  </tr> 
 </tbody> 
</table>

计算完Next数组，即可根据模式串不匹配下标进行指针回溯。根据上述图解依次进行匹配即可。

其中next数组的计算思想极其关键，以下详细说明：

(1)首先，模式串的next数组的0位置与1位置一定分别是0，1。

(2)定义两个指针i,j。其中i代表next数组下标，不回溯，而j代表next数组每个位置相应的元素。

对于模式串中第K个元素，其最大公共前后缀最大比K-1位置元素的公共前后缀大一（理想状态，char\[i\] == char\[j\]），否则，j指针回溯到数组j位置的值。

(3)依次执行步骤二即可。

## 三、KMP模式匹配算法代码实现 ##

1、计算next数组（以下代码下标是从一开始计算）

int* Get_Next(SString String)
    {
        int* arr = (int*)malloc(sizeof(int) * (String.longth+1));
       int i=1;
       int j=0;
       arr[1]=0;
       while(i<String.longth+1)
       {   
            
    		if(j==0||String.c[i-1]==String.c[j-1])
    		{
    			arr[++i]=++j;
    		}
    		else
    		{
    			j=arr[j];//看门牌
    		}
       	
       }
       printf("————————next数组计算完成————————\12") ; 
       return arr;
    };

2、实现KMP算法（String1和String2数组我的下标是从零开始）

int  Search_index(SString String1,SString String2,int* arr)
    {
    	int i = 0;//目标串指针 
    	int j = 0;//模式串指针 
    	while(1)
    	{
    		if(String1.c[i]==String2.c[j])
    		{
    			++i;
    			++j;
    		} 
    		else
    		{ 
    			if(j==0)
    			{
    				++i;
    			} 
    			else
    			{	
    				j = arr[j+1]-1;
    			}
    		}
    		if(j==String2.longth)
    		{
    			return i-String2.longth+1; 
    		}
    		if(String1.longth-i+1<String2.longth-j+1)//判断字符串比较何时结束 
    		{
    			return -1;
    		}
    	 } ;
    	
    };

3、以下是完整代码

#include <stdio.h>
    #include <stdlib.h>
    #include <String.h>
    #define MAXSIZE 50
    typedef struct {
        char c [MAXSIZE];
        int longth;
    }SString;
    //字符串模式匹配算法
    int* Get_Next( SString String2);//获取next数组
    int  Search_index(SString String1,SString String2,int*arr);
    int main()
    {
        SString String1;
        printf("请输入目标串：");
        scanf("%s", &String1.c);
        String1.longth=strlen(String1.c); 
        printf("输入成功\n");
        
        SString String2;
        printf("请输入模式串：");
        scanf("%s", &String2.c);
        String2.longth=strlen(String2.c); 
        printf("输入成功\n");
        int *arr=Get_Next(String2);
        int i = 0;
        for(i=1;i<=String2.longth;i++)
        {
        	printf("%d ",i);
        	printf("%d\n",arr[i]);
    	}
    	int n = Search_index( String1, String2,arr);
    	if(n==-1)
    	{
    		printf("Don't find the index!'");
    	}
    	else 
    	{
    		printf("坐标为%d",n);
    	}
    	return 0; 
    }
    int* Get_Next(SString String)
    {
        int* arr = (int*)malloc(sizeof(int) * (String.longth+1));
       int i=1;
       int j=0;
       arr[1]=0;
       while(i<String.longth+1)
       {   
            
    		if(j==0||String.c[i-1]==String.c[j-1])
    		{
    			arr[++i]=++j;
    		}
    		else
    		{
    			j=arr[j];//看门牌
    		}
       	
       }
       printf("————————next数组计算完成————————\12") ; 
       return arr;
    };
    int  Search_index(SString String1,SString String2,int* arr)
    {
    	int i = 0;//目标串指针 
    	int j = 0;//模式串指针 
    	while(1)
    	{
    		if(String1.c[i]==String2.c[j])
    		{
    			++i;
    			++j;
    		} 
    		else
    		{ 
    			if(j==0)
    			{
    				++i;
    			} 
    			else
    			{	
    				j = arr[j+1]-1;
    			}
    		}
    		if(j==String2.longth)
    		{
    			return i-String2.longth+1; 
    		}
    		if(String1.longth-i+1<String2.longth-j+1)//判断字符串比较何时结束 
    		{
    			return -1;
    		}
    	 } ;
    	
    };

[feefc3520ea24173b1806ed75ef20496.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/23/083324e94cb54177a62e8cf4f08868ca.png