`
housen1987
  • 浏览: 344898 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

串的模式匹配算法

阅读更多

子串定位运算又称为模式匹配(pattern matching)或串匹配(string matching)。

在串匹配中,将主串称为目标串,子串称为模式串。

关于串匹配的时间复杂度,在最坏的情况下:每一次合法位移后,在内循环中都要比较m个字符才能知道是不是有效位移,最坏的情况下时间复杂度是O([n-m+1]*m).


1 朴素的串匹配算法

int index(seqString *s,seqString *t){
    int i,j,k;
    for(i=0;i<s>len-t->len;i++){	
    	for(j=0,k=i;j<t->len && s->str[k]==t->str[j];k++,j++);
    	if(j==t->len) return i;
    }
    return -1;
}

    朴素的串匹配算法简单,但是效率低下。

2  “严蔚敏”版数据结构提供的算法

int index(seqString *s,seqString *t){
    int i=0,j=0;
    while(i<s->len && j <t->len){
    	if(s->str[i] == s->str[j]){
    		i++;j++;
    	}else{
    		i = i-j + 1;j = 0; //指针退后,重新匹配
    	}
    }
    if(j == t->len) return i-j;
    return -1;
}
 
分享到:
评论

相关推荐

    基于字符串模式匹配算法的病毒感染检测问题_算法_数据结构_

    字符串模式匹配算法在此过程中扮演了核心角色,因为它可以高效地查找可能的病毒签名或恶意代码序列。本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配...

    基于字符串模式匹配算法的病毒感染检测问题 实验四(源代码+实验报告)

    本实验“基于字符串模式匹配算法的病毒感染检测问题”聚焦于如何利用这些算法来识别潜在的恶意代码,从而预防计算机病毒感染。 《数据结构(C语言版 第2版)》一书由著名计算机科学家严蔚敏编著,书中涵盖了各种...

    字符串模式匹配算法的改进研究

    ### 字符串模式匹配算法的改进研究 #### 引言 随着网络安全问题的日益突出,网络入侵检测系统(Network Intrusion Detection System, NIDS)作为一项重要的安全防护技术,在网络安全领域受到了广泛的关注。模式...

    严蔚敏《数据结构》实验三:基于字符串模式匹配算法的病毒感染检测问题

    严蔚敏《数据结构》实验三:基于字符串模式匹配算法的病毒感染检测问题

    KMP_字符串模式匹配算法

    **KMP字符串模式匹配算法详解** KMP(Knuth-Morris-Pratt)算法是一种高效地在主串(text)中查找子串(pattern)的字符串模式匹配算法,由Dijkstra、Morris和Pratt在1970年提出。这个算法避免了不必要的字符比较,...

    数据结构实验 串模式匹配算法

    本实验“数据结构实验:串模式匹配算法”着重于研究如何在长字符串(主串)中查找一个特定的短字符串(模式串)。以下是对实验内容的详细阐述: 首先,我们来了解一下串的基本概念。在C++中,字符串通常用字符数组...

    数据结构实验-2串模式匹配算法(串实验)

    实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...

    KMP字符串模式匹配算法ppt

    KMP(Knuth-Morris-Pratt)字符串模式匹配算法是一种高效的字符串搜索算法,由D.M. Knuth、V. Morris和J.H. Pratt在1970年提出。该算法避免了简单匹配算法中的不必要的回溯,显著提高了在文本字符串中查找模式字符串...

    用C++实现BM的字符串模式匹配算法

    在计算机科学领域,字符串模式匹配是一项基础且重要的任务,它涉及到在文本中寻找特定模式的出现。本篇文章将深入探讨如何使用C++实现Bad Character Rule(坏字符规则)和Good Suffix Rule(好后缀规则)来优化Boyer...

    Kmp字符串模式匹配算法.doc

    KMP字符串模式匹配算法 KMP字符串模式匹配算法是一种高效的字符串搜索算法,由Donald Knuth、Vaughan Pratt和James H. Morris在1977年共同发表。该算法可以快速地在一大串字符中查找一个模式串的出现位置。 从标题...

    KMP字符串模式匹配算法

    KMP字符串模式匹配算法是一种高效的字符串搜索算法,由D.E.Knuth、V.R.Morris和J.W.Pratt三位学者提出,因此得名KMP算法。该算法避免了在匹配过程中不必要的字符回溯,提高了匹配效率。下面我们将深入探讨KMP算法的...

    字符串模式匹配算法[集合][精华]

    字符串模式匹配算法是计算机科学中一个重要的研究领域,它在文本处理、搜索引擎、生物信息学等领域有着广泛应用。本文将深入探讨这一主题,并基于压缩包文件中的资料,提供一系列相关知识点。 1. **基本概念** - *...

    精选_毕业设计_基于C语言的串模式匹配算法_完整源码

    在IT领域,串模式匹配算法是计算机科学中的一个重要分支,特别是在文本处理、数据搜索和信息安全等方面有着广泛应用。本文将深入探讨基于C语言实现的串模式匹配算法,以及它在毕业设计项目中的应用。 1. **C语言...

    一种字符串模式匹配算法的实现

    提供了一种新的字符串模式匹配算法的实现,而常规算法往往低效.字符串模式匹配算法是程序开发过程中应用非常广的重要算法.

    字符串的模式匹配算法——KMP

    字符串的模式匹配算法在计算机科学中占据着重要的地位,它主要应用于文本搜索、数据分析和文本处理等领域。KMP(Knuth-Morris-Pratt)算法是其中一种高效的算法,尤其适用于处理具有重复子串的模式匹配问题。接下来...

    字符串模式匹配算法比较-C++实现-Qt6完成GUI-完整源代码-包含测试数据链接

    这个项目“字符串模式匹配算法比较-C++实现-Qt6完成GUI-完整源代码”是针对合肥工业大学《程序设计与算法训练》(通常与《数据结构》课程相关)的一个课程设计任务。作者通过这个项目实践了多种字符串匹配算法,并...

    KMP字符串模式匹配算法[文].pdf

    KMP字符串模式匹配算法 KMP字符串模式匹配算法是一种高效的字符串匹配算法,通过对模式字符串的预处理生成next数组,来实现快速的字符串匹配。该算法的关键在于,当某个位置的匹配不成功时,根据之前的匹配结果,从...

Global site tag (gtag.js) - Google Analytics