第4章 串(2)

if(j==-1||s->data[i]==t->data[j]){ i++;j++; }

else j= next[j] ; if(j>=t->len)

return( i=t->len+1 ); else

return(-1); }

2、函数实现串的模式匹配算法，请在空格处将算法补充完整。 int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){ i++;j++; }else{

i= i-j+1 ;j=0; }

if(j>=t->len)

return i-t->len+1 ; else

return -1; }}/*listDelete*/

3、写出下面算法的功能。

int function(SqString *s1,SqString *s2){ int i;

for(i=0;ilength&&ilength;i++) if(s->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i]; return s1->length-s2->length; }

答案：.串比较算法 4、写出算法的功能。

int fun(sqstring *s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){ i++;j++; }else{

i=i-j+1;j=0; }

if(j>=t->len)

return i-t->len+1; else

return -1; }

答案：串的模式匹配算法

一、基本概念

1、串的概念

2、空串与空格串的区别 3、子串与主串 4、串相等 5、串比较

6、串的模式匹配

7、串的模式匹配算法（BF、KMP、注意指针i，j的变化，模式串的next值） 二、练习题

1．以下叙述中正确的是 。 A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中无素只能是字母 D.空串就是空白串 3．串是一中特殊的线性表，其特殊性体现在____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符