数据结构 | 每日一练（115）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．设 s、t 为两个字符串，分别放在两个一维数组中，m、n 分别为其长度，判断 t 是否为 s 的子串。如果是，输出子串所在位置（第一个字符），否则输出 0。（注：用程序实现）

正确答案

PS：||代表注释

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

int index( char s[],t[], int m,n)

//字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，

输出子串在s中的位置，否则输出0。

{ int i=0,j=0;

while (i<=m-n && j<=n-1)

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

else {i=i-j+1;j=0;} //对应字符不相等，I回溯，j仍为0。

if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1); return(i-n+1);}//匹配成功

else return(0); //匹配失败

}//算法index结束

main ()//主函数

{ char s[],t[]; int m,n,i;

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

scanf(“%s”,s); //输入主串

scanf(“%s”,t); //输入子串

i=index(s,t,m,n);

}//程序结束

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

-end-

长按关注

文 | 闫小林