C语言朴素模式匹配算法实例代码

一、什么是字符串的模式匹配？

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

注意：

①、子串——主串的一部分，一定存在。

②、模式串——不一定能在主串中找到

二、朴素模式匹配算法

主串长度为n，模式串长度为m。

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串匹配对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

最多对比n-m+1个子串

（一）通过数组下标实现朴素模式匹配算法

若当前⼦串匹配失败，则主串指针 i 指向下⼀个⼦串的第⼀个位置，模式串指针 j 回到模式串的第⼀个位置

若 j > T.length，则当前⼦串匹配成功，返回当前⼦串第⼀个字符的位置 —— i - T.length

int Index(SString S, SString T){
	int i=1,j=1;
	while(i <= S.length && j<=T.length){
		if(S.ch[i]==T.ch[j]){
			++i;
			++j;	//继续比较后继字符
		}
		else{
			i=i-j+2;
			j=1;	//指针后退重新开始匹配
		}
	}
	if(j > T.length)
		return i-T.length;
	else
		return 0;
}

（二）时间复杂度

设主串⻓度为 n，模式串⻓度为 m，则

①、最坏时间复杂度 = O(nm)

②、最好时间复杂度 = O(n) 1. 最坏时间复杂度O(nm)

最坏的情况，每个⼦串都要对⽐ m 个字符，共 n-m+1 个⼦串，复杂度 = O((n-m+1)m) = O(nm)

注：很多时候，n >> m

2. 最好时间复杂度O(n)

最好的情况，每个⼦串的第⼀个字符就匹配失败，共 n-m+1 个⼦串，复杂度 = O(n-m+1) = O(n)

注：很多时候，n >> m

总结

到此这篇关于C语言朴素模式匹配算法的文章就介绍到这了,更多相关C语言朴素模式匹配算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 使用C语言解决字符串匹配问题的方法

    最常想到的方法是使用KMP字符串匹配算法: #include <stdio.h> #include <stdlib.h> #include <string.h> int get_nextval(char *pattern, int next[]) { //get the next value of the pattern int i = 0, j = -1; next[0] = -1; int patlen = strlen(pattern); while ( i &l

  • C语言实现字符串匹配KMP算法

    C语言实现字符串匹配KMP算法

    字符串匹配是计算机的基本任务之一. 举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"? 下面的的KMP算法的解释步骤 1. 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较.因为B与A不匹配,所以搜索词后移一位. 2. 因为B与A不匹配,搜索词再往后移. 3. 就这样,直到字符

  • C语言数据结构之模式匹配字符串定位问题

    C语言数据结构之模式匹配字符串定位问题 主要实现了三种字符串的模式匹配,主要包括字符串子操作的集合,字符串指针回溯,和KMP算法 头文件  #ifndef INDEXHEAD_H_INCLUDED #define INDEXHEAD_H_INCLUDED #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 255 typedef char Sstring[MAXLEN + 1

  • C语言朴素模式匹配算法实例代码

    C语言朴素模式匹配算法实例代码

    一.什么是字符串的模式匹配? 字符串模式匹配:在主串中找到与模式串相同的子串,并返回其所在位置. 注意: ①.子串--主串的一部分,一定存在. ②.模式串--不一定能在主串中找到 二.朴素模式匹配算法 主串长度为n,模式串长度为m. 朴素模式匹配算法:将主串中所有长度为m的子串依次与模式串匹配对比,直到找到一个完全匹配的子串,或所有的子串都不匹配为止. 最多对比n-m+1个子串 (一)通过数组下标实现朴素模式匹配算法 若当前⼦串匹配失败,则主串指针 i 指向下⼀个⼦串的第⼀个位置,模式串指针 j

  • Go语言实现遗传算法的实例代码

    在没介绍正文之前先给大家补充点go语言基本知识及实例. Go 语言教程 Go 是一个开源的编程语言,它能让构造简单.可靠且高效的软件变得容易. Go是从2007年末由Robert Griesemer, Rob Pike, Ken Thompson主持开发,后来还加入了Ian Lance Taylor, Russ Cox等人,并最终于2009年11月开源,在2012年早些时候发布了Go 1稳定版本.现在Go的开发已经是完全开放的,并且拥有一个活跃的社区. Go 语言特色 简洁.快速.安全 并行.有

  • php实现 master-worker 守护多进程模式的实例代码

    具体代码如下所示: <?php class Worker{ public static $count = 2; public static function runAll(){ static::runMaster(); static::moniProcess(); } //开启主进程 public static function runMaster(){ //确保进程有最大操作权限 unmask(0); $pid = pcntl_fork(); if($pid > 0){ echo "

  • C语言动态顺序表实例代码

    C语言动态顺序表实例代码

    目录 顺序表概念: 一.准备工作 二.顺序表的基本操作  1.顺序表的初始化函数 2.尾插函数(在尾部插入数据) 3.头插函数(在数组头部插入数据)  4.尾删函数 5.头删函数 6.在第pos的位置插入数据 7.删除第pos个位置的数据 8.修改第pos个位置的数据 9.查找函数. 10.销毁函数 11.打印函数 三.总代码: 顺序表概念:         顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.一般情况下用数组存储.在数组上完成数据的增删查改. 代码解析: 一.准备工

  • C语言打印各种图案实例代码

    1.线段图案 #include<stdio.h> int main() { int a = 0; while(~scanf("%d",&a)) { int i = 0; for(i=0;i<a;i++) { printf("*"); } printf("\n"); } return 0; } 2.正方形图案 #include<stdio.h> int main() { int a = 0; while(~sc

  • C语言实现三子棋实例代码

    我是半自主的完成了这个程序,看了B站鹏哥视频并仔细思索后才做出来的,我没有完全采用他的方法,导致程序还有一些不足之处,还请各位大佬指出. 首先,我将该程序的实现分为3个板块,main,game.h,和game.c; 代码如下: #define _CRT_SECURE_NO_WARNINGS #include"game.h" void menu() { printf("****************************************\n"); prin

  • C语言音乐播放器实例代码

    C语言音乐播放器实例代码

    实例代码如下: #include <stdio.h> #include<dirent.h> #include<stdlib.h> #include<unistd.h> #include<string.h> typedef struct node_ node_t; struct node_{ char* name;//gequming node_t * prev; node_t * next; }; node_t *head = NULL; int

  • C 语言插入排序算法及实例代码

    插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的. 在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素.第一轮时,将第一个元素作为排序好的子数组,插入第二个元素:第二轮,将前两个元素作为排序好的数组,插入第三个元素.以此类

  • C语言合并排序及实例代码

    C语言合并排序及实例代码

    归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并.仅从算法思想上了解归并排序会觉得很抽象,接下来就以对序列A[0], A[l]-, A[n-1]进行升序排列来进行讲解,在此采用自顶向下的实现方法. 操作步骤如下: (1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first

  • java实现Composite组合模式的实例代码

    java实现Composite组合模式的实例代码

    //20210121 写在前面:刚期末考试完,考了面向对象,里边儿有23个设计模式,我寻思着考完挨个儿实现一下,本文实现组合模式 组合模式核心思想类似文件夹的概念,构件树形结构,树形有叶子结点和文件夹结点,文件夹结点可以包含叶子结点和文件夹结点 分为两种模式 - 透明型:所有节点构造全部相同,但是由于叶子结点没有下层结点,所以其有些方法为空,会不安全 - 安全型:叶子结点和文件架节点构造不同,这样展示的时候需要判断节点属性,不方便调用,但是由于没有空方法,会很安全 透明型组合模式程序源代码: /

随机推荐