数据结构考研笔记（十四） ——串的模式匹配

女爷i 2022-12-16 06:06 202阅读 0赞

## 串的模式匹配 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][20201018221933112.png_pic_center]

int Index (SString S, sString T,int pos) {
        
    int i=pos,j=1;//i为主串标记  j为模式串标记
    while(i<=s.length & j<=T.length) {
          
    	if(s.ch[i]= T.ch[j1) {
        //判断第一个字符是否相等
    		i++;
    		j++;
    	}
    	else {
        
    		i=i-j+2;//下移一个位置
    		j=1;//模式串归为1
    	}
    	if (j>T. length)
    		return i-T.length;//相同，返回第一个位置
    	else
    		return 0;//没有匹配的
    ]

时间复杂度O（nm）  
**例子**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f2a2235d64664e17ad1a9356313a19b6.png
[20201018221933112.png_pic_center]: /images/20221123/aa1585ea8d8746ba8683e03163355dea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/37613142400c4409976459801038a103.png

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构考研学习笔记（七）---串

串 1. 串的定义和实现 1.1 串的定义 1.2 串的存储结构 1.2.1 定义顺序存储表示

阳光穿透心脏的1/2处/ 2023年03月14日 08:05/ 0 赞/ 153 阅读

相关【数据结构】-串的模式匹配

串的模式匹配写在前面 1.头文件及类型定义 2.串类型定义 3.函数声明 4.基本操作 4.1 初始化串 4.2

ゝ一世哀愁。/ 2023年03月01日 12:39/ 0 赞/ 20 阅读

相关 2022年考研数据结构_4 串

https://gitee.com/fakerlove/Data-Structure 文章目录 4. 串 4.1 模式匹配

ゞ浴缸里的玫瑰/ 2022年12月31日 05:22/ 0 赞/ 354 阅读

相关串的模式匹配算法设计（数据结构学习笔记）

文章目录 BF算法、KMP算法 BF算法算法过程算法代码串的定义

谁借莪１个温暖的怀抱￠/ 2022年12月28日 04:20/ 0 赞/ 213 阅读

相关数据结构考研笔记（十七）——图的概念

图图的基本概念无向图&有向图简单图&多重图完全图子图无向图& 有向图

Dear 丶/ 2022年12月16日 06:16/ 0 赞/ 183 阅读

相关数据结构考研笔记（十四） ——串的模式匹配

串的模式匹配 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9

女爷i/ 2022年12月16日 06:06/ 0 赞/ 203 阅读

相关数据结构考研笔记（十三）——二叉排序树

二叉排序树 1.二叉排序树 2.查找 3.插入 4.构造 5.删除 6.查找效率 1

╰+哭是因爲堅強的太久メ/ 2022年12月16日 06:00/ 0 赞/ 231 阅读

相关数据结构考研笔记（十）--------数组矩阵

数组数组是由n (n>=1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素受n个线性关系的约束，每个元素在n个线性关系中的序号称

谁践踏了优雅/ 2022年12月13日 04:48/ 0 赞/ 226 阅读

相关《数据结构》—— 串的模式匹配算法

串的模式匹配一、简单的模式匹配算法（BF算法）二、KMP算法一、简单的模式匹配算法（BF算法）在实际应用中我们常常能用到类似串的

一时失言乱红尘/ 2022年09月12日 04:47/ 0 赞/ 309 阅读

相关《数据结构》KMP 串的模式匹配

题目给定两个由英文字母组成的字符串 String 和 Pattern，要求找到 Pattern 在 String 中第一次出现的位置，并将此位置后的 String 的子

Dear 丶/ 2022年04月13日 05:15/ 0 赞/ 371 阅读