C语言数据结构(10)--串的改进模式匹配算法(KMP)

布满荆棘的人生 2022-12-09 13:56 127阅读 0赞

***[点此查看全部文字教程、视频教程、源代码][Link 1]***

### 本文目录 ###

*  1. KMP概述
 *  2. 代码实现

# 1. KMP概述 #

改进的匹配算法，又称为KMP算法。当匹配过程中发现主串和模式串字符不等，主串的字符位置指针不再回退，而是利用之前匹配的信息将模式串的匹配位置尽可能的移动，再继续比较的算法。

KMP算法还是相当复杂的，说实话我看了好几个小时才稍微理解了，此处附上一篇我感觉讲的比较到位的博客：[详解KMP算法][KMP]。

# 2. 代码实现 #

虽然算法比较复杂，但是实现起来代码量很小，佩服！

/*
    * 主题：KMP模式匹配算法
    * 作者：熊猫大大
    * 时间：2020-09-22
    */
    #include <stdio.h>
    // 获取子串的next数组
    void getNext(char *pattern,int next[]) 
    {
        
    	//初始化变量
    	int i, j, len;
    	len = strlen(pattern);
    	i = 0;
    	j = -1;
    	next[0] = -1;//固定值
    	// 循环设置next数组每个位置的值
    	while (i < len) 
    	{
        
    		if (j == -1 || pattern[i] == pattern[j]) 
    		{
        
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else 
    		{
        
    			j = next[j];
    		}
    	}
    }
    // kmp模式匹配 -1表示匹配失败，其他值表示匹配位置
    int kmpIndex(char *main,char* pattern,int next[]) 
    {
        
    	// 初始化变量
    	int i, j, mainLen, patternLen;
    	i = 0;
    	j = -1;
    	mainLen = strlen(main);
    	patternLen = strlen(pattern);
    	// 查找匹配串的位置
    	while (i < mainLen&&j < patternLen) 
    	{
        
    		// 通过next快速调整j的位置
    		if (j == -1 || main[i] == pattern[j]) 
    		{
        
    			i++;
    			j++;
    		}
    		else
    		{
        
    			j = next[j];
    		}
    	}
    	if (j >= patternLen) //匹配成功
    	{
        
    		return i - patternLen;
    	}
    	else //失败
    	{
        
    		return -1;
    	}
    }
    
    int main()
    {
        
    	char * pattern = "bcd";
    	int* next= (int*)malloc(sizeof(int)*strlen(pattern));
    	getNext(pattern,next);
    	char * main = "abcd";
    	printf("位置：%d", kmpIndex(main, pattern, next));
    }

[Link 1]: https://studyingpanda.blog.csdn.net/article/details/105329926
[KMP]: https://www.cnblogs.com/caiyishuai/p/10701166.html