数据结构考研分类复习真题 第四章 答案[12]

五算法设计

[题目分析]判断字符串t是否是字符串s的子串称为串的模式匹配其基本思想是对串s和t各设一个指针i和ji的值域是mnj的值域是n初始值i和j均为模式匹配从s和t开始若s=t则i和j指针增加若在某个位置si!=tj则主串指针i回溯到i=ij+j仍从开始进行下一轮的比较直到匹配成功（j>n）返回子串在主串的位置（ij）否则当i>mn则为匹配失败

int index(char s[]t[]int mn)//字符串s和t用一维数组存储其长度分别为m和n本算法求字符串t在字符串s中的第一次出现如是输出子串在s中的位置否则输出

{int i=j=;

while (i<=mn && j<=n)

if (s[i]==t[j]){i++;j++;}//对应字符相等指针后移

else {i=ij+;j=;}//对应字符不相等I回溯j仍为

if(i<=mn && j==n) {printf(t在s串中位置是%din+);return(in+);}//匹配成功

else return(); //匹配失败

}//算法index结束

main ()//主函数

{char s[]t[]; int mni;

scanf(%d%d&m&n);//输入两字符串的长度

scanf(%ss);//输入主串

scanf(%st);//输入子串

i=index(stmn);

}//程序结束

[程序讨论]因用C语言实现一维数组的下标从开始m是主串最后一个字符的下标n是t串的最后一个字符的下标若匹配成功最佳情况是s串的第到第n个字符与t匹配时间复杂度为o（n）;匹配成功的最差情况是每次均在t的最后一个字符才失败直到s串的第mn个字符成功其时间复杂度为o（（mn）*n）即o（m*n）失败的情况是s串的第mn个字符比t串某字符比较失败时间复杂度为o（m*n）之所以串s的指针i最大到mn是因为在mn之后所剩子串长度已经小于子串长度n故不必再去比较算法中未讨论输入错误（如s串长小于t串长）

另外根据子串的定义返回值in+是子串在主串中的位置子串在主串中的下标是in

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []