串的形式匹配算法

串的模式匹配算法

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