实现KMP字符串匹配

港控/mmm° 2023-05-22 08:43 65阅读 0赞

KMP 字符串匹配算法可以实现高效的匹配。  
假设长字符串为t，短字符串为p。为了进行 KMP 匹配，首先需要计算字符串p的next数组，后面实现了计算该数组的函数void KmpGenNext(char\* p, int\* next)。对于 “abcabcab” ，计算出的next数组如下图：  
![在这里插入图片描述][20200416194431755.png]  
其中：next\[i\]给出如下信息：从左到右将p的字符与t的字符进行比对时，若在p的i号位置出现不匹配，就将字符串p相对t右移i-next\[i\]位；若next\[i\]>=0，则右移后比对位置从next\[i\]号位置开始，否则从0号位置开始。下图 1 给出了一个匹配示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]  
输入输出格式：  
输入格式：  
第一行输入母串  
第二行输入子串  
输出格式：  
输出Location: \#，其中\#是子串在母串中的位置编号样例输入：  
样例输入：  
stringabcedf1stringabcdef2stringabcdef3stringabcdef4stringabcdef5stringabcdef6stringabcdef7  
stringabcdef7  
样例输出：  
Location: 78

#include <stdio.h>
    #include <stdlib.h>
    #include "kmp.h"
    void KmpGenNext(char* p, int* next)
    //生成p的next数组, next数组长度大于等于字符串p的长度加1
    { 
        next[0]= -1;
        int k= -1;
        for (int i=1; p[i-1]!=0; i++) 
        {     
            while(k>=0&&p[k]!=p[i-1])   
      	{ 
       		k=next[k];
       		k=k+1; 
       		if (p[i]==p[k])  
       		{ 
        			next[i]=next[k];
       		}
         		else    
       		{ 
        			next[i]=k;
       		}
      	}
        }
    }
    int KmpFindSubWithNext(char* t, char* p, int* next)
    //从t中查找子串p的第一次出现的位置
    //若找到，返回出现的位置，否则返回-1
    { 
        int i=0, j=0;
        while(p[i]!=0 && t[j]!=0)    
        { 
            if(p[i]==t[j])     
      	{  
                i++;  
                j++; 
            }
            else  if (next[i]>=0) 
      	{ 
                i = next[i];
            }
            else  
      	{  
                i=0;  
                j++; 
            }
        }
        if(p[i]==0)  
        { 
      	return j-i; //found
        }
        else  
        { 
      	return -1;  //not found
        }
    }

[20200416194431755.png]: /images/20230521/ad90a4f9e4084149b2c61fc93141d2dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]: /images/20230521/ad2a136476b248d0a7c2e73e9c8e980b.png