C语言数据结构(9)--串的朴素模式匹配算法

Myth丶恋晨 2022-12-09 02:48 192阅读 0赞

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

### 本文目录 ###

*  1. 模式匹配概念
 *  2. 朴素的模式匹配算法
 *  3. 朴素模式匹配代码实现

# 1. 模式匹配概念 #

查找字符串子串的位置的操作，称为串的模式匹配，子串被称为模式串。

串的模式匹配是非常高频的操作，具体如何去匹配的算法也很重要。

# 2. 朴素的模式匹配算法 #

朴素模式匹配算法也称为布鲁特-福斯算法，感觉很是高大上，但是实现起来很简单。

朴素的意思就是最符合咱们朴素思维的算法，从主串的第一个字符开始与子串进行比对，如果相等则逐一比对后续字符；如果不等则从主串第二个字符开始匹配子串，直到发现全部相等的子串。

# 3. 朴素模式匹配代码实现 #

两层循环就可以解决，完整代码如下：

#include <stdio.h>
    #define MAX_LENGTH 100
    /*
    * 主题：串的朴素模式匹配算法
    * 作者：熊猫大大
    * 时间：2020-01-15
    */
    
    //字符串结构体
    typedef struct {
        
    	char content[MAX_LENGTH];//内容部分，最后一位存储'\0',所以实际字符串内容长度是MAX_LENGTH-1
    	int length;//实际长度
    }String;
    
    //打印字符串
    void printStr(String *str)
    {
        
    	printf("str:%s\n", str->content);
    }
    
    //请空字符串
    void clearStr(String *str)
    {
        
    	str->content[0] = '\0';
    	str->length = 0;
    }
    
    //返回字符串长度
    int getStrLength(String *str)
    {
        
    	return str->length;
    }
    
    //判断字符串是否为空 是1 否0
    int isEmpty(String *str)
    {
        
    	if (str->length == 0)
    	{
        
    		return 1;
    	}
    	else
    	{
        
    		return 0;
    	}
    }
    
    //添加字符
    int appendChar(String *str, char c)
    {
        
    	if (str->length < MAX_LENGTH - 1)
    	{
        
    		str->content[str->length] = c;
    		str->length++;
    		str->content[str->length] = '\0';
    		return 1;
    	}
    	else //长度不足，返回失败0
    	{
        
    		return 0;
    	}
    }
    
    //插入字符,index从0开始,注意需要将后面的字符全部向后挪一个位置
    int insertChar(String *str, int index, char c)
    {
        
    	int i;
    	if (str->length < MAX_LENGTH - 1)
    	{
        
    		for (i = str->length; i >= index; i--) //从最后一个'\0'开始都向后移动一个位置
    		{
        
    			str->content[i + 1] = str->content[i];
    		}
    		str->content[index] = c;//将插入元素放入指定位置
    		return 1;
    	}
    	else //长度不足，返回失败0
    	{
        
    		return 0;
    	}
    }
    
    //删除指定位置元素，index从0开始，直接从后面往前覆盖即可
    int deleteChar(String *str, int index)
    {
        
    	int i;
    	for (i = index; i <= str->length; i++)
    	{
        
    		str->content[i] = str->content[i + 1];
    	}
    	return 1;
    }
    
    //将str2连接到str1
    int concat(String *str1, String *str2)
    {
        
    	int i = 0;
    	int leftLength = MAX_LENGTH - 1 - str1->length;//剩余可用长度
    	if (leftLength < str2->length) {
        //长度不足返回失败
    		return 0;
    	}
    	//依次取出str2中元素追加到str1
    	for (i = 0; i < str2->length; i++)
    	{
        
    		appendChar(str1, str2->content[i]);
    	}
    	return 1;
    }
    
    // 朴素模式匹配，返回值-1匹配失败，其他返回值为匹配成功的起始位置
    int index(String *str1, String *str2) {
        
    	int position = 0;//从主串0位置开始
    	int i = 0;
    	while (position < str1->length) {
        
    		for (i = 0; i < str2->length; i++) {
        //匹配子串
    			if (position + i > str1->length - 1) {
        
    				break;
    			}
    			if (!(str1->content[position + i] == str2->content[i])) {
        
    				break;
    			}
    		}
    		if (i == str2->length) {
        //全部走完没跳出，匹配成功
    			return position;
    		}
    		position++;
    	}
    	return -1;
    }
    
    int main()
    {
        
    	// 定义str1
    	String str1;
    	clearStr(&str1);
    	appendChar(&str1, 'a');
    	appendChar(&str1, 'b');
    	appendChar(&str1, 'c');
    	appendChar(&str1, 'd');
    	printf("str1:\n");
    	printStr(&str1);
    	// str2测试
    	String str2;
    	clearStr(&str2);
    	appendChar(&str2, 'b');
    	appendChar(&str2, 'c');
    	appendChar(&str2, 'd');
    	printf("str2:\n");
    	printStr(&str2);
    	// 模式匹配
    	printf("匹配结果：%d\n",index(&str1, &str2));
    
    }

[Link 1]: https://studyingpanda.blog.csdn.net/article/details/105329926