基于C语言的串模式匹配算法

Hydra

发布日期: 2019-09-29 07:20:02 浏览量: 76
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验要求

1.1 实现功能

从主串中第K个字符起,求出子串在主串中首次出现的位置,即模式匹配或串匹配。

要求用三种模式匹配算法分别实现:

  • 朴素的模式匹配算法(BF算法)

  • KMP改进算法(Next[ ])

  • KMP改进算法(NextVal[ ])

1.2 设计要求

首先设计一个含有多个菜单项的主控菜单程序,然后再为这些菜单项配上相应的功能。

程序运行后,给出5个菜单项的内容和输入提示:

  • 1.输入主串、子串和匹配起始位置

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

  • 3.KMP改进算法(Next[ ])

  • 4.KMP改进算法(NextVal[ ])

  • 0.退出管理系统

请选择0—4:

  • 菜单设计要求:使用数字0—4来选择菜单项,其它输入则不起作用

  • 输出结果要求:输出各趟匹配详细过程(其中3、4,首先输出Next[ ]或者NextVal[ ]的各元素的数值),然后输出匹配总趟数、单个字符比较次数、匹配成功时的位置序号或者匹配失败提示信息

二、实验步骤

2.1 程序流程图

2.1.1 主函数流程图

2.1.2 Input函数流程图

2.1.3 Output函数流程图

2.1.4 getNext_val函数流程图

2.1.5 Index_BF函数流程图

2.1.6 Index_Next函数流程图

2.1.7 Index_NextVal函数流程图

2.1.8 getNext函数流程图

2.2 主函数源码

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. void Input(char* str1, char* str2, int* pos); //输入主串、模式串、匹配位置的函数
  5. void Index_BF(char* str1, char* str2, int pos); //朴素的匹配算法
  6. void Index_Next(char* str1, char* str2, int pos); //KMP算法
  7. void Index_NextVal(char* str1, char* str2, int pos); //KMP改进算法(NextVal[])
  8. void Output(char* str); //输出主串或模式串
  9. void getNext(char *str1, int* &next); //计算next数组的值
  10. void getNext_val(char* str2, int* &nextval);
  11. void main()
  12. {
  13. int choice;
  14. char str1[1000];
  15. char str2[100];
  16. int pos;
  17. while(1)
  18. {
  19. printf("请选择功能:\n");
  20. printf("1.输入主串、子串和匹配起始位置\n");
  21. printf("2.朴素的模式匹配算法\n");
  22. printf("3.KMP改进算法(Next[])\n");
  23. printf("4.KMP改进算法(NextVal[])\n");
  24. printf("0.退出管理系统\n");
  25. scanf("%d", &choice);
  26. switch(choice)
  27. {
  28. case 1:
  29. Input(str1, str2, &pos);
  30. break;
  31. case 2:
  32. Index_BF(str1, str2, pos);
  33. break;
  34. case 3:
  35. Index_Next(str1, str2, pos);
  36. break;
  37. case 4:
  38. Index_NextVal(str1, str2, pos);
  39. break;
  40. case 0:
  41. return;
  42. default:
  43. printf("输入数字错误\n");
  44. }
  45. }
  46. }

2.3 运行结果截图

2.3.1 主函数运行结果

2.3.2 Input函数运行结果

2.3.3 Index_BF函数运行结果

2.3.4 Index_Next函数运行结果

2.3.5 Index_NextVal函数运行结果

三、总结与体会

在该实验中,我实现了几种模式匹配算法,并通过程序输出匹配的过程,让我对课本上的理论知识有了更深层次的理解。

这些程序还有些不完美的地方,可能有些算法实现地比较复杂,有些地方写出来之后不具有普遍性,只针对某种特殊情况。这些不完美的地方在之后我还会尽量修改。

上传的附件 cloud_download 基于C语言的串模式匹配算法.7z ( 1.06mb, 1次下载 )
error_outline 下载需要6点积分

发送私信

希望从来不会放弃你,是你放弃了希望

15
文章数
23
评论数
最近文章
eject