AI 助理
备案控制台
开发者社区 人工智能 文章 正文

串的模式匹配相关问题（BF算法、KMP算法）

2023-10-10 151
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 串的模式匹配相关问题（BF算法、KMP算法）

一、字符串中删除子串

【问题描述】编写一个程序，当在一个字符串中出现子串时就删除它（字符串的字符个数不超过1000）。

【输入形式】第一行输入一个字符串，第二行输入一个子串。

【输出形式】程序在下一行输出删除其中所有子串后的字符串。如果字符串不包含子串则输出原字符串本身。

【样例输入1】

I am a boy!

a            

【样例输出1】

I m  boy!      

【样例输入2】    

Ah Love!could you and I with Fate conspire

ould

【样例输出2】

Ah Love!c you and I with Fate conspire

【样例说明】

删除第一个字符串中所有的子串，包括连续出现的子串。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 128
#define INCREAM 10
typedef struct String{
  char *data;
  int len;
  int size;
}String,*PString;
int Init_String(PString S){              //初始化
  S->data=(char *)malloc(sizeof(char)*SIZE);
  S->len=0;
  S->size=SIZE;
  return 1;
}
int Creat_String(PString S,char *s){    //串的赋值
  int i=0;
  int n=strlen(s);
  while(*s!='\0'){
    if(S->size<n){
      S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char));
      S->size+=INCREAM;
    }
    S->data[i++]=*s++;
    S->len++;
  }
  return 1;
}
int Index_BF(PString S1,PString S2,int start){    //BF算法
  int i=start-1,j=0;
  while(i<S1->len&&j<S2->len){
    if(S1->data[i]==S2->data[j]){
      i++;
      j++;
    }else{
      i=i-j+1;
      j=0;
    }
  }
  if(j>=S2->len){
    return i-S2->len+1;
  }else{
    return 0;
  }
}
int Print_String(PString S){   
  int i;
  for(i=0;i<S->len;i++){
    printf("%c",S->data[i]);
  }
  printf("\n");
  return 1;
}
int Delete_String(PString S,PString T){      //删除操作
  int i,j,k,t;
  for(i=0;i<S->len;i++){      
    if(Index_BF(S,T,1))       //找到要删除子串在主串的位置
    {
        t=Index_BF(S,T,1);         
        for(j=0;j<T->len;j++){        //删除次数为子串的长度
          for(k=t-1;k<S->len-1;k++){   
            S->data[k]=S->data[k+1];
        }
        S->len--;     //每次删除一个字符后，串的长度减 1
      } 
    }
  }
    return 1;
}
int main(){
  char s1[100],s2[100];
  int next[100];
  String S1,S2;
  Init_String(&S1);
  Init_String(&S2);
  gets(s1);
  gets(s2);
  Creat_String(&S1,s1);
  Creat_String(&S2,s2);
  Delete_String(&S1,&S2);
    Print_String(&S1);
    return 0;
}

二、BF 算法

【问题描述】

串的模式匹配算法BF的应用。

【输入形式】

第一行输入主串s；

第二行输入模式串t；

输入串中均不包含空格字符。

【输出形式】

模式串在主串s中的出现的每一个位置序号。若一次都未匹配到，则输出0。

【样例输入1】

ababcabcacbab

ab

【样例输出1】

1 3 6 12

【样例输入2】

111113455113232342432432

11

【样例输出2】

1 2 3 4 10

【样例输入3】

fasdfdsfsadfdsdsagetgrdgfdgdf

2312

【样例输出3】

0

【评分标准】

采用BF算法。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 128
#define INCREAM 10
typedef struct String{
  char *data;
  int len;
  int size;
}String,*PString;
int Init_String(PString S){
  S->data=(char *)malloc(sizeof(char)*SIZE);
  S->len=0;
  S->size=SIZE;
  return 1;
}
int Creat_String(PString S,char *s){
  int i=0;
  int n=strlen(s);
  while(*s!='\0'){
    if(S->size<n){
      S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char));
      S->size+=INCREAM;
    }
    S->data[i++]=*s++;
    S->len++;
  }
  return 1;
}
int Index_BF(PString S1,PString S2,int start){   //BF算法
  int i=start-1,j=0;
  while(i<S1->len&&j<S2->len){
    if(S1->data[i]==S2->data[j]){
      i++;
      j++;
    }else{
      i=i-j+1;
      j=0;
    }
  }
  if(j>=S2->len){
    return i-S2->len+1;
  }else{
    return 0;
  }
}
int Prints_String(PString S,PString T){
  int x;
  x=Index_BF(S,T,1);
  if(x==0) printf("0\n");   
  while(x!=0){
    printf("%d ",x);
    x=Index_BF(S,T,x+1);   //下一次遍历从当前字符后面一个字符开始
  }
  return 1;
}
int main(){
  char s1[100],s2[100];
  int next[100];
  String S1,S2;
  Init_String(&S1);
  Init_String(&S2);
  gets(s1);
  gets(s2);
  Creat_String(&S1,s1);
  Creat_String(&S2,s2);
    Prints_String(&S1,&S2);
    return 0;
}

三、KMP 算法

【问题描述】

串的模式匹配算法实现（KMP算法）

【输入形式】

第一行输入主串s；

第二行输入模式串t；

第三行输入起始位置pos；

【输出形式】

输出模式串t的next值（以空格分隔）

输出模式匹配结果

【样例输入1】

ababcabcacbab

abcac

1

【样例输出1】

-1 0 0 0 1

6

【评分标准】

采用kmp算法。(next值从-1开始)  

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 128
#define INCREAM 10
typedef struct String{
  char *data;
  int len;
  int size;
}String,*PString;
int Init_String(PString S){
  S->data=(char *)malloc(sizeof(char)*SIZE);
  S->len=0;
  S->size=SIZE;
  return 1;
}
int Creat_String(PString S,char *s){
  int i=0;
  int n=strlen(s);
  while(*s!='\0'){
    if(S->size<n){
      S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char));
      S->size+=INCREAM;
    }
    S->data[i++]=*s++;
    S->len++;
  }
  return 1;
}
int Next_String(PString S,int next[]){   //Next数组
  int i=0,j=-1;
  next[0]=-1;
  while(i<S->len){
    if((j==-1)||(S->data[i]==S->data[j])){
      i++;
      j++;
      next[i]=j;
    }else{
      j=next[j];
    }
  }
  for(i=0;i<S->len;i++){
    printf("%d ",next[i]);
  }
  printf("\n");
  return 1;
}
int Index_KMP(PString S,PString T,int start,int next[]){   //KMP算法
  int i=start-1,j=0;
  while(i<S->len&&j<T->len){
    if(j==-1||S->data[i]==T->data[j]){
      i++;
      j++;
    }else{
      j=next[j];    //next数组
    }
  }
  if(j>=T->len){
    printf("%d\n",i-T->len+1);
  }else{
    printf("0\n");
  }
}
int main(){
  char s1[100],s2[100];
  int next[100];
  String S1,S2;
  Init_String(&S1);
  Init_String(&S2);
  gets(s1);
  gets(s2);
  Creat_String(&S1,s1);
  Creat_String(&S2,s2);
    Next_String(&S2,next);
    Index_KMP(&S1,&S2,1,next);
    return 0;
}

四、带通配符“？”的模式匹配

【问题描述】

编写一个具有通配符？的模式匹配算法。?可以与任意一个字符匹配。

【输入形式】

输入主串s；

输入子串t；

输入起始位置pos。

【输出形式】

输出匹配结果：子串第一次出现的位置，若未找到，输出0。

【样例输入1】

there are many cats.

?re

1

【样例输出1】

3

【样例输入2】

thsdfiewnjf fsdfdsjewd

f??f

3

【样例输出2】

13

【样例说明】

?为英文状态符号。由于输入串中可能含有空格，请使用gets读入字符串。

【评分标准】

采用kmp或者bf算法均可。

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define SIZE 128
#define INCREAM 10
typedef struct String{
  char *data;
  int len;
  int size;
}String,*PString;
int Init_String(PString S){
  S->data=(char *)malloc(sizeof(char)*SIZE);
  S->len=0;
  S->size=SIZE;
  return 1;
}
int Creat_String(PString S,char *s){
  int i=0;
  int n=strlen(s);
  while(*s!='\0'){
    if(S->size<n){
      S->data=(char*)realloc(S->data,(S->size+INCREAM)*sizeof(char));
      S->size+=INCREAM;
    }
    S->data[i++]=*s++;
    S->len++;
  }
  return 1;
}
int Index2_BF(PString S1,PString S2,int start){   //BF算法
  int i=start-1,j=0;
  while(i<S1->len&&j<S2->len){
    if((S1->data[i]==S2->data[j])||S2->data[j]=='?'){   //在BF算法中加一个条件即可
      i++;
      j++;
    }else{
      i=i-j+1;
      j=0;
    }
  }
  if(j>=S2->len){
    printf("%d ",i-S2->len+1);
  }else{
    printf("0\n");
  }
}
int main(){
  char s1[100],s2[100];
  int next[100];
  String S1,S2;
  Init_String(&S1);
  Init_String(&S2);
  gets(s1);
  gets(s2);
  Creat_String(&S1,s1);
  Creat_String(&S2,s2);
    int n;
    scanf("%d",&n);
    Index2_BF(&S1,&S2,n);
    return 0;
}

a3f46dd0ffac49a785ab6381a75d637c.png


07ee2900ef084a748d2a2b7ed635ccca.png

文章标签：
算法
关键词：
算法kmp
bf算法kmp
算法bf
算法模式匹配
模式匹配bf算法kmp
Want595
目录
相关文章
游客jrsavpvegh62y
|
2月前
|
算法 搜索推荐
如何用CRDT算法颠覆文档协作模式？
在局域网环境下，高效文档协同编辑面临版本冲突等核心技术挑战，影响协作效率和成果质量。为解决此问题，可采用基于CRDT的算法，允许多用户无冲突实时编辑；或将协同操作模块化，通过任务看板优化协作流程，减少冲突，提高团队效率。未来，局域网协同编辑将更加场景化与个性化，深入探索组织协作文化。
游客jrsavpvegh62y
47 2
游客u4xnihpexalb6
|
4月前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析：算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码，指导如何将核心功能转化为技术实现，涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
游客u4xnihpexalb6
148 0
Codelinghu
|
4月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
Codelinghu
40 0
廖文
|
4月前
|
算法
KMP算法
KMP算法
廖文
54 0
风吹落叶花飘荡
|
6月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现，包括计算模式串的next数组和在主串中查找模式串位置的函数，用于演示KMP算法的基本应用。
风吹落叶花飘荡
74 1
readmancynn
|
6月前
|
算法
KMP算法
KMP算法
readmancynn
48 0
泥腿子架构师
|
7月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
泥腿子架构师
77 0
简简单单做算法
|
2天前
|
算法 数据安全/隐私保护 计算机视觉
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果，无水印展示。使用Matlab 2022a和Vivado 2019.2开发，提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放，并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放，确保质量。
简简单单做算法
106 74
简简单单做算法
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印，使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出，旨在分离图像的光照和反射分量，增强图像对比度、颜色和细节，尤其在雾天条件下表现优异，有效解决图像去雾问题。
简简单单做算法
116 71
软件算法开发
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真，适用于动态环境下的自主导航。使用MATLAB2022A版本运行，展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣（目标方向性、障碍物距离、速度一致性），实时调整机器人运动参数，确保安全避障并接近目标。
软件算法开发
147 68

热门文章

最新文章

  • 1
    图解前向、反向传播算法，一看就懂！
  • 2
    利用SVM(支持向量机)分类算法对鸢尾花数据集进行分类
  • 3
    通过算法备案之后就万事大吉了么？
  • 4
    算法备案全流程攻略：保姆级教程
  • 5
    C 408—《数据结构》算法题基础篇—链表（下）
  • 6
    使用贪心算法解决最小生成树问题
  • 7
    C 408—《数据结构》算法题基础篇—链表（上）
  • 8
    Transformer打破三十年数学猜想！Meta研究者用AI给出反例，算法杀手攻克数学难题
  • 9
    【算法合规新时代】企业如何把握“清朗·网络平台算法典型问题治理”专项行动？
  • 10
    Java线程调度揭秘：从算法到策略，让你面试稳赢！
  • 1
    C语言数据结构算法，常用10种排序实战
    91
  • 2
    用伪代码表示算法
    138
  • 3
    AES算法逆向实战--某思路
    166
  • 4
    【优选算法】——滑动窗口——1004. 最大连续1的个数 III
    62
  • 5
    【优选算法】——滑动窗口——3. 无重复字符的最长子串
    60
  • 6
    [优选算法]------滑动窗⼝——209. 长度最小的子数组
    64
  • 7
    【优选算法】——双指针——18. 四数之和
    58
  • 8
    【优选算法】——双指针——15. 三数之和
    52
  • 9
    【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
    75
  • 10
    【优选算法】——Leetcode——611. 有效三角形的个数
    66

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型