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

女爷i 2022-12-16 06:06 105阅读 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 条评论，105人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关数据结构---串的朴素模式匹配算法

导言数据结构中的串就是我们常说的字符串，当我们需要在一个长字符串中寻找目标字符串的时候就需要一种算法来进行定位目标字符串，下面记录一个目标字符串匹配算法----朴素模式

た入场券/ 2022年10月16日 09:48/ 0 赞/ 191 阅读

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

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

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

相关数据结构---串的模式匹配算法介绍

前言 The years teach much which the days never knew. Time:2017/2/19 Name:Willam 1、介

小灰灰/ 2022年07月12日 08:58/ 0 赞/ 226 阅读

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

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

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