欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

串的模式匹配算法

程序员文章站 2022-07-14 15:24:02
...

子串定位运算又称为模式匹配(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;
}