devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法库应用--Brute - Force算法串匹配(顺序串)

作者：你好赵伟 | 2024-07-10 12:22:00

赞

踩

算法库应用--Brute - Force算法串匹配(顺序串)

学习贺利坚老师关于B-F算法的算法库

数据结构例程——串的模式匹配（Brute-Force算法）_sqstring s, t; strassign(s,"ababcabcacbabcaccab");-CSDN博客

本人规则解析博客

串的匹配 (Brute - Force 算法)_brute force算法-CSDN博客\

版本更新日志

V1.0: 在原有的博客基础上, 加入我构建的算法库, 让博客更完全 , 代码可以运行看效果, 不是让算法仅仅停留在 逻辑方面, 这也是后续我努力的方向, 把这些算法模型, 尽可能的去运用到实际的嵌入式项目中, 把理论变成实物 , 本次也进行了名字优化, 让逻辑更清晰

V1.0

功能函数

利用B-f算法,寻找子串在母串中的位置

  1. /**************************************************
  2. 函数名: Find_matching_location
  3. 功  能: 利用B-f算法,寻找子串在母串中的位置
  4. 参  数: (1)Sequential_string Mother_String:母串
  5.         (2)Sequential_string Son_String:子串
  6. 思  路:  从开始逐个对比,如果对比不成功, 则起始位置前移, 计数器初始化, 直到超出长度或找到
  7. 注  意:   我们判断是否找到的标志,就是判断 子串计数器是否对比完,然后跳出
  8. 返回值:  int: -1--没找到, 其他:找到,返回其数组位序
  9. **************************************************/
  10. int Find_matching_location(Sequential_string Mother_String,Sequential_string Son_String)
  11. {
  12.     int Mother_counter,Son_counter;//同步计数器
  13.     int Mother_begin;//每次对比从母串开始的位置
  14.     Mother_counter = 0;
  15.     Son_counter = 0;
  16.     Mother_counter = 0;
  17.     //Brute-Force算法
  18.     while((Mother_begin+Mother_counter) < Mother_String.length && Son_counter < Son_String.length)
  19.     {
  20.         if(Mother_String.Sequential_string_data[Mother_begin+Mother_counter] == Son_String.Sequential_string_data[Son_counter])
  21.         {
  22.             Mother_counter++;
  23.             Son_counter++;
  24.         }
  25.         else
  26.         {
  27.             Mother_begin++;
  28.             Mother_counter = 0;
  29.             Son_counter = 0;
  30.         }
  31.     }
  32.     //通过判断子串计数器的溢出数值,得出是否找到
  33.     if(Son_counter >= Son_String.length)
  34.     {
  35.         return Mother_begin;
  36.     }
  37.     else
  38.     {
  39.         return (-1);
  40.     }
  41. }

调用的顺序串算法库

头文件

Sequential_string.h
  1. #ifndef _SEQUENTIAL_STRING_H_INCLUDE
  2. #define _SEQUENTIAL_STRING_H_INCLUDE
  3.  
  4. #include <stdio.h>
  5. #define MaxSize 100 //最多字符个数
  6.  
  7. //顺序串数据结构
  8. typedef struct
  9. {
  10.     char Sequential_string_data[MaxSize];//数组串数据
  11.     int length;                          //实际串长
  12. }Sequential_string;
  13.  
  14. //(1)将一个字符串数组赋值给顺序串
  15. void Assignment_Sequential_string(Sequential_string &New_String, char Assign_array[]);
  16. //(2) 复制一个串,到另一个串
  17. void Copy_Sequential_String(Sequential_string &accept_string, Sequential_string copy_string);
  18. //(3)判断两个串是否相等
  19. bool Equal_Sequential_String(Sequential_string judge_string1, Sequential_string judge_string2);
  20. //(4)求顺序串串长
  21. int Length_Sequential_String(Sequential_string measure_string);
  22. //(5)串连接
  23. Sequential_string Connect_Sequential_String(Sequential_string link1, Sequential_string link2);
  24. //(6)求子串(从begin_loation开始的number个字符)
  25. Sequential_string Get_Sequential_Substring(Sequential_string substring, int begin_loation, int number);
  26. //(7)插入串(从从begin_loation开始插入字符串,然后组合成新的串)
  27. Sequential_string Insert_Sequential_String(Sequential_string old_string, int begin_loation,Sequential_string insert_string);
  28. //(8)删除串(从begin 开始的number个字符)
  29. Sequential_string Delete_Sequential_String(Sequential_string old_string, int begin_loation,int number);
  30. //(9)串替换(从begin 开始的number个字符)
  31. Sequential_string Replace_Sequential_String(Sequential_string old_string, int begin_loation,int number,Sequential_string new_string);
  32. //(10)输出展示串
  33. void Display_Sequential_String(Sequential_string show_String);
  34. #endif

库函数

Sequential_string.cpp
  1. #include "Sequential_string.h"
  2.  
  3. /**************************************************
  4. (1)函数名: Assignment_Sequential_string
  5. 功  能: 将一个字符串数组赋值给顺序串
  6. 参  数: (1)Sequential_string &New_String:创建的新串
  7.         (2)char Assign_array[]: 原始字符串数组
  8. 注  意:  顺序数组,结尾加入'\0'
  9. 返回值: 无
  10. **************************************************/
  11. void Assignment_Sequential_string(Sequential_string &New_String, char Assign_array[])
  12. {
  13.     int counter;
  14.     for(counter = 0; Assign_array[counter] != '\0'; counter++)
  15.     {
  16.         New_String.Sequential_string_data[counter] = Assign_array[counter];
  17.     }
  18.     New_String.Sequential_string_data[counter] = '\0';
  19.     New_String.length = counter;    //更新串最大位序
  20. }
  21.  
  22. /**************************************************
  23. (2)函数名: Copy_Sequential_String
  24. 功  能: 复制一个串,到另一个串
  25. 参  数: (1)Sequential_string &accept_string: 复制成的串
  26.         (2)Sequential_string copy_string:要复制的串
  27. 注  意:  复制成的串,传回的是地址,所以不用传回参数
  28. 返回值: 无
  29. **************************************************/
  30. void Copy_Sequential_String(Sequential_string &accept_string, Sequential_string copy_string)
  31. {
  32.     int counter;
  33.     for(counter = 0; counter < copy_string.length;counter++)
  34.     {
  35.         accept_string.Sequential_string_data[counter] = copy_string.Sequential_string_data[counter];
  36.     }
  37.     accept_string.Sequential_string_data[counter] = '\0';
  38.     accept_string.length = copy_string.length;
  39. }
  40. /**************************************************
  41. (3)函数名: Equal_Sequential_String
  42. 功  能: 判断两个串是否相等
  43. 参  数: (1)Sequential_string judge_string1:第一个串
  44.         (2)Sequential_string judge_string2:第二个串
  45. 返回值: bool?是否相等,true:false
  46. **************************************************/
  47. bool Equal_Sequential_String(Sequential_string judge_string1, Sequential_string judge_string2)
  48. {
  49.     bool same = true;
  50.     int counter;
  51.     if(judge_string1.length != judge_string2.length)
  52.     {
  53.         same = false;
  54.     }
  55.     else
  56.     {
  57.         for(counter = 0; counter < judge_string1.length;counter++)
  58.         {
  59.             if(judge_string1.Sequential_string_data[counter] != judge_string2.Sequential_string_data[counter])
  60.             {
  61.                 same = false;
  62.                 break;
  63.             }
  64.         }
  65.     }
  66.     return same;
  67.  
  68. }
  69.  
  70. /**************************************************
  71. (4)函数名: Length_Sequential_String
  72. 功  能: 求顺序串串长
  73. 参  数: Sequential_string measure_string:要进行测量的串
  74. 返回值: int:顺序串长度信息
  75. **************************************************/
  76. int Length_Sequential_String(Sequential_string measure_string)
  77. {
  78.     return measure_string.length;
  79. }
  80.  
  81. /**************************************************
  82. (5)函数名: Connect_Sequential_String
  83. 功  能: 把两个串连接成一个串
  84. 参  数: Sequential_string link1, Sequential_string link2:两个要链接的串
  85. 返回值: 返回Sequential_string Connection_string: 链接成的串
  86. **************************************************/
  87. Sequential_string Connect_Sequential_String(Sequential_string link1, Sequential_string link2)
  88. {
  89.     Sequential_string Connection_string;
  90.     int counter;
  91.     Connection_string.length = link1.length + link2.length;
  92.     //将第一个串加入链接的串
  93.     for(counter = 0; counter < link1.length; counter++)
  94.     {
  95.         Connection_string.Sequential_string_data[counter] = link1.Sequential_string_data[counter];
  96.     }
  97.     //将第二个串加入链接的串
  98.     for(counter = 0; counter < link2.length; counter++)
  99.     {
  100.         Connection_string.Sequential_string_data[link1.length+counter] = link2.Sequential_string_data[counter];
  101.     }
  102.     Connection_string.Sequential_string_data[link1.length+counter] = '\0';
  103.     return Connection_string;
  104. }
  105.  
  106. /**************************************************
  107. (6)函数名: Get_Sequential_Substring
  108. 功  能: 求子串(从begin_loation开始的number个字符)
  109. 参  数: (1)Sequential_string mother_String:母串
  110.         (2)int begin_loation:开始分割子串的位置
  111.         (3)int number:子串的数量
  112. 返回值: Sequential_string son_String:得到的子串
  113. **************************************************/
  114. Sequential_string Get_Sequential_Substring(Sequential_string mother_String, int begin_loation, int number)
  115. {
  116.     Sequential_string son_String;
  117.     int counter;
  118.     son_String.length = 0;
  119.     if(begin_loation <= 0 || begin_loation > mother_String.length || number < 0 || begin_loation+number-1>mother_String.length)
  120.     {
  121.         //错误:分割的子字符串的位置错误。
  122.         printf("\nError<6>:The position of the divided substring is wrong.\n");
  123.         return son_String; //    参数不正确返回空串
  124.     }
  125.     for(counter = begin_loation-1; counter < begin_loation+number-1; counter++)
  126.     {
  127.         son_String.Sequential_string_data[counter-begin_loation+1] = mother_String.Sequential_string_data[counter];
  128.     }
  129.     son_String.Sequential_string_data[counter-begin_loation+1] = '\0';
  130.     son_String.length = number;
  131.     return son_String;
  132. }
  133.  
  134. /**************************************************
  135. (7)函数名: Insert_Sequential_String
  136. 功  能: 插入串(从从begin_loation开始插入字符串,然后组合成新的串)
  137. 参  数: (1)Sequential_string old_string:在原始串的基础上插入
  138.         (2)int begin_loation: 插入的位置
  139.         (3)Sequential_string insert_string:插入的新串
  140. 思  路:  在原有串的基础上,割开一个口子,放上新串,然后组合成新串
  141. 返回值: Sequential_string form_string:组合成的新串
  142. **************************************************/
  143. Sequential_string Insert_Sequential_String(Sequential_string old_string, int begin_loation,Sequential_string insert_string)
  144. {
  145.     int counter;
  146.     Sequential_string form_string;
  147.     form_string.length = 0;
  148.     //参数不正确, 返回空串
  149.     if(begin_loation <= 0 || begin_loation > old_string.length+1)
  150.     {
  151.         //错误:插入位置错误
  152.         printf("\nError<7>: wrong insertion position.\n");
  153.         return form_string;
  154.     }
  155.     for(counter = 0; counter < begin_loation-1;counter++)
  156.     {
  157.         form_string.Sequential_string_data[counter] = old_string.Sequential_string_data[counter];
  158.     }
  159.  
  160.     for(counter = 0; counter < insert_string.length;counter++)
  161.     {
  162.         form_string.Sequential_string_data[begin_loation-1+counter] = insert_string.Sequential_string_data[counter];
  163.     }
  164.  
  165.     for(counter = begin_loation-1; counter<old_string.length;counter++)
  166.     {
  167.         form_string.Sequential_string_data[insert_string.length+counter] = old_string.Sequential_string_data[counter];
  168.     }
  169.     form_string.Sequential_string_data[insert_string.length+counter] = '\0';
  170.     form_string.length = old_string.length + insert_string.length;
  171.     return form_string;
  172.  
  173. }
  174. /**************************************************
  175. (8)函数名: Delete_Sequential_String
  176. 功  能: 删除串(从begin 开始的number个字符)
  177. 参  数: (1)Sequential_string old_string:在原有串的基础上删除
  178.         (2)int begin_loation: 开始删除的位置(从逻辑1开始)
  179.         (3)int number:删除的数量
  180. 注  意:  要判断删除的位置和数量是否正确
  181. 返回值:Sequential_string new_string:删除完后的新串
  182. **************************************************/
  183. Sequential_string Delete_Sequential_String(Sequential_string old_string, int begin_loation,int number)
  184. {
  185.     int counter;//定义计数器
  186.     Sequential_string new_string;
  187.     new_string.length = 0;
  188.     //合法性判断(begin_loation理应从1开始到leng长度)
  189.     if(begin_loation <= 0 || begin_loation > old_string.length || (begin_loation+number-1) > old_string.length)
  190.     {
  191.         //错误:删除的位置或数量错误。
  192.         printf("Error<8>: Wrong location or quantity of deletion.");
  193.         return new_string;//返回空串
  194.     }
  195.     //择出删除位置之前的串
  196.     for(counter = 0; counter < begin_loation-1;counter++)
  197.     {
  198.         new_string.Sequential_string_data[counter] = old_string.Sequential_string_data[counter];
  199.     }
  200.     //择出删除位置之后的串
  201.     for(counter = begin_loation+number-1; counter < old_string.length; counter++)
  202.     {
  203.         new_string.Sequential_string_data[counter-number] = old_string.Sequential_string_data[counter];
  204.     }
  205.     new_string.Sequential_string_data[counter-number] = '\0';
  206.     new_string.length = old_string.length - number;
  207.     return new_string;
  208. }
  209.  
  210. /**************************************************
  211. (9)函数名: Replace_Sequential_String
  212. 功  能: 串替换(从begin 开始的number个字符)
  213. 参  数: (1)Sequential_string old_string:原始串
  214.         (2)int begin_loation:开始替换的位置
  215.         (3)int number:替换的字符个数
  216.         (4)Sequential_string replace_string:要替换成的字符串
  217. 思  路: 锁定old_string从begin_loation开始的number个字符,
  218.         然后开始剪切建立新串,
  219.         ①把begin_loation之前的字符加入新串,
  220.         ②要替换成的串加入,
  221.         ③锁定后的字符加入
  222.         ④组合成新串,返回传出
  223. 注  意:  最后加'\0'
  224. 返回值: Sequential_string new_string:替换后,产生的新串
  225. **************************************************/
  226. Sequential_string Replace_Sequential_String(Sequential_string old_string, int begin_loation,int number,Sequential_string replace_string)
  227. {
  228.     int counter;
  229.     Sequential_string new_string;
  230.     new_string.length = 0;
  231.     //合法性判断
  232.     if(begin_loation <= 0 || begin_loation > old_string.length || begin_loation+number-1>old_string.length)
  233.     {
  234.         //错误:要替换位置出现错误
  235.         printf("\nError<9>: There is an error in the position to be replaced.\n");
  236.         return new_string;//返回空串
  237.     }
  238.     //开始复制剪切
  239.     for(counter = 0; counter < begin_loation-1; counter++)
  240.     {
  241.         new_string.Sequential_string_data[counter] = old_string.Sequential_string_data[counter];
  242.     }
  243.     //加入要替换的串
  244.     for(counter = 0; counter < replace_string.length; counter++)
  245.     {
  246.         new_string.Sequential_string_data[begin_loation-1+counter] = replace_string.Sequential_string_data[counter];
  247.     }
  248.     //被替换位置,后面剩余的串
  249.     for(counter = begin_loation+number-1; counter < old_string.length; counter++)
  250.     {
  251.         new_string.Sequential_string_data[counter-number+replace_string.length] = old_string.Sequential_string_data[counter];
  252.     }
  253.     new_string.Sequential_string_data[counter-number+replace_string.length] = '\0';
  254.     new_string.length = old_string.length - number + replace_string.length;
  255.     return new_string;
  256. }
  257.  
  258.  
  259.  
  260. /**************************************************
  261. (10)函数名: Display_Sequential_String
  262. 功  能: 输出展示串
  263. 参  数: Sequential_string show_String:要输出展示的串
  264. 注  意: 字符串后续可以换成自定义类型
  265. 返回值: 无
  266. **************************************************/
  267. void Display_Sequential_String(Sequential_string show_String)
  268. {
  269.     int counter;
  270.     if(show_String.length > 0)
  271.     {
  272.         for(counter = 0; counter < show_String.length; counter++)
  273.         {
  274.             printf("%c", show_String.Sequential_string_data[counter]);
  275.         }
  276.         printf("\n");
  277.     }
  278. }

main函数调用

  1. int main()
  2. {
  3.     //在母串里面找子串
  4.     Sequential_string Mother_String;
  5.     Sequential_string Son_String;
  6.  
  7.     char Mother_String_array[] = {'a','b','a','b','c','a','b','c','a','c','b','a','b','\0'};
  8.     char Son_String_array[] = {'a','b','c','a','c','\0'};
  9.     //把两个字符串创建成字符串
  10.     Assignment_Sequential_string(Mother_String, Mother_String_array);
  11.     Assignment_Sequential_string(Son_String, Son_String_array);
  12.     printf("\nMother_String:\n");
  13.  
  14.     Display_Sequential_String(Mother_String);
  15.     printf("\nSon_String:\n");
  16.     Display_Sequential_String(Son_String);
  17.     printf("\n%d\n",Find_matching_location(Mother_String,Son_String));
  18.  
  19.     return 0;
  20. }

main.cpp源码(包含功能函数)

main.cpp
  1. #include <stdio.h>
  2. #include "Sequential_string.h"
  3.  
  4. /**************************************************
  5. 函数名: Find_matching_location
  6. 功  能: 利用B-f算法,寻找子串在母串中的位置
  7. 参  数: (1)Sequential_string Mother_String:母串
  8.         (2)Sequential_string Son_String:子串
  9. 思  路:  从开始逐个对比,如果对比不成功, 则起始位置前移, 计数器初始化, 直到超出长度或找到
  10. 注  意:   我们判断是否找到的标志,就是判断 子串计数器是否对比完,然后跳出
  11. 返回值:  int: -1--没找到, 其他:找到,返回其数组位序
  12. **************************************************/
  13. int Find_matching_location(Sequential_string Mother_String,Sequential_string Son_String)
  14. {
  15.     int Mother_counter,Son_counter;//同步计数器
  16.     int Mother_begin;//每次对比从母串开始的位置
  17.     Mother_counter = 0;
  18.     Son_counter = 0;
  19.     Mother_counter = 0;
  20.     //Brute-Force算法
  21.     while((Mother_begin+Mother_counter) < Mother_String.length && Son_counter < Son_String.length)
  22.     {
  23.         if(Mother_String.Sequential_string_data[Mother_begin+Mother_counter] == Son_String.Sequential_string_data[Son_counter])
  24.         {
  25.             Mother_counter++;
  26.             Son_counter++;
  27.         }
  28.         else
  29.         {
  30.             Mother_begin++;
  31.             Mother_counter = 0;
  32.             Son_counter = 0;
  33.         }
  34.     }
  35.     //通过判断子串计数器的溢出数值,得出是否找到
  36.     if(Son_counter >= Son_String.length)
  37.     {
  38.         return Mother_begin;
  39.     }
  40.     else
  41.     {
  42.         return (-1);
  43.     }
  44. }
  45.  
  46.  
  47. int main()
  48. {
  49.     //在母串里面找子串
  50.     Sequential_string Mother_String;
  51.     Sequential_string Son_String;
  52.  
  53.     char Mother_String_array[] = {'a','b','a','b','c','a','b','c','a','c','b','a','b','\0'};
  54.     char Son_String_array[] = {'a','b','c','a','c','\0'};
  55.     //把两个字符串创建成字符串
  56.     Assignment_Sequential_string(Mother_String, Mother_String_array);
  57.     Assignment_Sequential_string(Son_String, Son_String_array);
  58.     printf("\nMother_String:\n");
  59.  
  60.     Display_Sequential_String(Mother_String);
  61.     printf("\nSon_String:\n");
  62.     Display_Sequential_String(Son_String);
  63.     printf("\n%d\n",Find_matching_location(Mother_String,Son_String));
  64.  
  65.     return 0;
  66. }
  67.

运行结果展示:

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号