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)); }
