数据结构串的模式匹配算法--BF暴力匹配

BF（Brute-Force，暴力匹配）算法是一种简单的字符串匹配算法，其基本思想是将目标串S逐个字符与模式串P进行比对，直到找到匹配或遍历完S为止。下面是一个使用C语言实现的BF算法示例：

#include <stdio.h>  
#include <string.h>  // BF算法实现  
// 参数：text是文本串，pattern是模式串  
// 返回值：如果找到模式串，则返回模式串在文本串中的起始位置（从0开始计数）；如果未找到，则返回-1  
int BF(const char* text, const char* pattern) {  int textLen = strlen(text);  int patternLen = strlen(pattern);  // 遍历文本串  for (int i = 0; i <= textLen - patternLen; i++) {  int j;  // 遍历模式串  for (j = 0; j < patternLen; j++) {  // 如果当前字符不匹配，则跳出内层循环  if (text[i + j] != pattern[j]) {  break;  }  }  // 如果j等于模式串长度，说明模式串匹配成功  if (j == patternLen) {  return i; // 返回模式串在文本串中的起始位置  }  }  // 未找到匹配的模式串  return -1;  
}  int main() {  const char* text = "hello world, welcome to the world of programming!";  const char* pattern = "world";  int index = BF(text, pattern);  if (index != -1) {  printf("Pattern found at index: %d\n", index);  } else {  printf("Pattern not found.\n");  }  return 0;  
}

第二种代码实现，是基于链串的结构体

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  #define SIZE 50  typedef struct Node {  char data[SIZE + 1];  int length;  struct Node* next;  
} Node;  Node* createNode(const char* str) {  Node* newnode = (Node*)malloc(sizeof(Node));  if (newnode == NULL) {  perror("malloc failed");  exit(EXIT_FAILURE);  }  strncpy(newnode->data, str, SIZE);  newnode->data[SIZE] = '\0';  newnode->length = strlen(newnode->data);  newnode->next = NULL;  return newnode;  
}  int BF(Node* s1, Node* s2) {  int i = 0, j = 0;  while (i < s1->length - s2->length + 1) {  j = 0;  while (j < s2->length && s1->data[i + j] == s2->data[j]) {  j++;  }  if (j == s2->length) {  return i; // 返回匹配开始的位置  }  i++; // 移动到文本串的下一个字符  }  return -1; // 未找到匹配  
}  int main() {  Node* arr1 = createNode("fanjunxi");  Node* arr2 = createNode("xi");  printf("arr1: %s\n", arr1->data);  printf("arr2: %s\n", arr2->data);  int index = BF(arr1, arr2);  if (index != -1) {  printf("子串开始于位置: %d\n", index);  } else {  printf("无符合的子串\n");  }  free(arr1);  free(arr2);  return 0;  
}

第三种代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSTRLEN 255   		//用户可在255以内定义最长串长typedef int Status;typedef struct {char str[MAXSTRLEN + 1];int len;
} SString;Status StrAssign(SString *T, char *chars) { //生成一个其值等于chars的串Tint i;if (strlen(chars) > MAXSTRLEN)return ERROR;else {T->len = strlen(chars);for (i = 1; i <= T->len; i++)T->str[i] = *(chars + i - 1);return OK;}
}//算法4.1　BF算法
int Index(SString S, SString T, int pos)
{//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0//其中，T非空，1≤pos≤StrLength(S)int i = pos;int j = 1;while(i <= S.len && j <= T.len){if(S.str[i] == T.str[j]){++i;++j;} //继续比较后继字符else{i = i - j + 2;j = 1;} //指针后退重新开始匹配}if (j > T.len)return i - T.len;elsereturn 0;return 0;
}//Indexint main()
{SString S;StrAssign(&S,"bbaaabbaba");SString T;StrAssign(&T,"abb");printf("主串和子串在第%d个字符处首次匹配\n", Index(S,T,1));return 0;
}