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

本文主要是介绍数据结构串的模式匹配算法--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;  
}

这篇关于数据结构串的模式匹配算法--BF暴力匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---