子串定位运算又称为模式匹配(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;
}
分享到:
相关推荐
字符串模式匹配算法的改进研究.pdf 字符串模式匹配算法的改进研究.pdf
基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
用C++实现BM的字符串模式匹配算法,两个代码分别实现坏字符规则和好后缀规则
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
字符串的模式匹配算法——KMP的C++实现。
提供了一种新的字符串模式匹配算法的实现,而常规算法往往低效.字符串模式匹配算法是程序开发过程中应用非常广的重要算法.
Kmp字符串模式匹配算法.doc
一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
KMP字符串模式匹配算法[文].pdf
基于C语言的串模式匹配算法
《KMP字符串模式匹配算法》教学课例[参照].pdf
《KMP字符串模式匹配算法》教学课例[归纳].pdf
一种新的串模式匹配算法,韩雷钧,张凯,模式的匹配算法一直是计算机搜索领域的研究的重点工程。本文首先分析了传统的蛮力字符串匹配和增强型的Boyer-Moore算法,并提出了一�