IntelliJ IDEA 数据库 网站favicon图标制作 二代征信 redux cmake uwp vue滑动事件 系统后台模板 pmp教学视频 jquery获取元素 db2从入门到精通 java算法培训 oracle查看数据库 mysql查看锁表 pip环境变量配置 linux获取当前时间 js原生点击事件 hadoop环境变量配置 反函数的二阶导数 python手册 python抛出异常 python函数的调用 python传参 java运算符 java获取当前年份 java重写和重载的区别 java开发环境安装 java读取文件数据 java数组最大值 轮播图js代码 ezcad2 字幕提取 2k14生涯模式修改器 god2iso 说话不算数的经典语句 数组删除指定元素 社区网格化管理平台 论文修改软件 完美漂移辅助
当前位置: 首页 > 学习教程  > 编程语言

串的模式匹配算法

2021/1/13 19:45:02 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

串的模式匹配算法串的模式匹配算法朴素匹配串的模式匹配算法 朴素匹配 这里采用C语言编写,使用串的定长存储,定义如下: // 顺序串的最大串长 #define MAX_STR_LEN 255 // 0号单元存放串的长度 typedef unsigned char SString[MAX_STR…

串的模式匹配算法

  • 串的模式匹配算法
    • 朴素匹配

串的模式匹配算法

朴素匹配

这里采用C语言编写,使用串的定长存储,定义如下:


// 顺序串的最大串长
#define MAX_STR_LEN 255       

// 0号单元存放串的长度
typedef unsigned char SString[MAX_STR_LEN + 1];      
 

基本思想:从主串的第pos个字符开始,和模式串的第一个字符依次比较,若相同,则往后逐个比较模式串后续字符。若不等,则从珠串的下一个字符开始从头和模式串的字符相匹配。时间复杂度:最好情况下是O(n+m);最坏时间复杂度为O(n*m),在匹配01串的时候往往效率会比较低。

算法实现如下:


int Index(SString  S,SString T,int post=1) {
    int i =post;
    int j =1;
    while (i<=S[0]&&j<=T[0]){
        if (S[i]==T[j]){
            i++;
            j++;
        } else{
            i = i-j+2;
            j=1;
        }
    }
    if (j>T[0]) return i-T[0]+1;
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_600167.shtml

附件下载

上一篇:20210113

下一篇:准召率理解

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?