字符串匹配-北京尧图网络

主字符串s模式字符串t字符串匹配就是找出字符串t首次出现在s的下标位置1BF算法暴力算法概述根据平时的经验将模式字符串从头开始一个个与主字符串比对需要两层循环外层循环是控制主字符串要和模式字符串匹配时的起点内层循环便是每次都要将模式字符串从头开始遍历。这样的算法时间复杂度高2KMP算法时间复杂度低常用概述主要是求解模式字符串t的next根据模式字符串的next数组在匹配时进行移动。求解next的方法1下标从1开始默认next[1]0next[2]1;2从第3个元素开始计算next值。首先是看这个元素的前一个元素对应的next值找第next个元素(记作)是否和这个相等或者说一样如果相等则该元素对应的next是其前一个元素对应的next值1如果不相等则需要继续回溯找对应的next值找第next个元素的字符是否和一样如果一样那这个元素对应的next值等于此时找到的这个元素的所属位置就是在字符串中是第几个元素也可以说是这个元素的下标1的个数1如果还是没找到就继续回溯3但如果知道回溯到第一个元素也不相等的话我们就让这个元素的next0。匹配的方法1设置代表两个字符串的下标i,j分别设置为1不要搞混因为next的下标我们是从0开始的但字符串的下标是从0开始的这里设置1之后后续需要注意-12开始遍历两个字符串如果对应的字符相等下标分别向后移动继续对比3如果不等这时候需要借助我们的next。我们首先是需要保持我们主字符的下标i保持不动将模式字符的下标jnext[j]意思就是将下标j设置为此时字符对应的next值之后主字符从i,模式字符从新的对应下标为j的元素开始遍历对比遇到不一样的继续保持i不变jnext[j]需要注意如果遇到j0那么需要将i和j同时14当i或者j的大小超过我们所给对应的字符长度的时候遍历就结束了。结束之后我们可以对比j和模式字符串的长度如果j大于模式字符串的长度说明模式字符串已经被匹配上了那么返回(i-模式字符串的长度因为i此时的位置是与模式字符串匹配到尾对应的个数要返回匹配成功的第一个元素的下标。#include stdio.h #include string.h #include stdlib.h //被查找的字符串为模式串我们就是要查找模式串第一次出现在字符串的位置 //朴素匹配 int strMatch(char *str,char *pattern){ int nstrlen(str); int mstrlen(pattern); for(int i0;i(n-m);i){ int j0; while(jm){ if(str[i]pattern[j]){ i; j; }else{ ii-j; break; } } if(jm){ return i-j; } } return -1; } //KMP算法 //基于模式串确定next数组利用next数组完成字符串匹配在匹配过程中发生字符不匹配中next数组用俩帮助确定下一次的匹配位置 void get_next(char *s,int *next){ next[1]0; next[2]1; int nstrlen(s); int i3; int knext[i-1]; while(in){ if(s[k-1]s[i-1]){ next[i]next[i-1]1; knext[i]; i; }else{ knext[k]; if(k0){ next[i]1; knext[i]; i; } } } } int PiPei(char *s1,char *s2){ int *next(int *)malloc(sizeof(int)*strlen(s2)); get_next(s2,next); int index11,index21; int len1strlen(s1),len2strlen(s2); while(index1len1index2len2){ if(s1[index1-1]s2[index2-1]){ index1; index2; }else{ index2next[index2]; if(index20){ index1; index2; } } } if(index2len2){ return index1-len2-1; }else{ return -1; } } int main(){ char s1[]abcbbabc; char s2[]ba; strstr(s1,s2);//返回s2在s1第一次出现的位置 printf(\n); printf(%p\n,strstr(s1,s2));//对应输出的地址 for(int i0;i3;i){ printf(%p ,s1[i]); } //朴素匹配 int posstrMatch(s1,s2); printf(%d\n,pos); printf(%d\n,PiPei(s1,s2)); }

字符串匹配

相关推荐

深入pdfcn Registry机制：shadcn CLI如何用一条命令安装PDF组件

Adobe 软件安装提示msvcp110.dll 缺失怎么办？手把手教你搞定

【实战】STM32 ADC采集数据乱跳？从参考源选型到软件滤波的工程调优笔记（附HAL库完整代码）

更多资讯

SpringBoot+Vue+MyBatis在线考试系统：开发部署与避坑指南

SSM+Vue教工公寓管理系统毕业设计：从项目搭建到论文答辩全指南

基于ZooKeeper的在线状态漂移检测与选主实现

专科生AI辅助开题报告：9个实用工具、完整流程与学术诚信红线

SpringBoot+Vue停车场管理系统毕设全解析：从架构设计到部署实战

VRChat头像性能优化：避免“贪多”工程，打造高评分角色

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？