子串定位函数的时问复杂度在最坏情况下为0（n×m）因此子串定位函数没有实际使用的价值。

A、15

B、16

C、17

D、18

对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串＜1，0，0，1，0，1，0，1，＞和＜0，1，0，1，1，0，1，1，＞的最长公共子序列的长度为(58)。

A．分治

B．贪心

C．动态规划

D．分支一限界

●试题五

阅读以下程序说明和C程序，将应填入(n)处的子句，写在答卷纸的对应栏内。

【程序说明】

函数int commstr(char *str1,char *str2,int *sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。

函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。

【程序】

int strlen(char *s)

{char *t=s；

while(*++)；

return t-s-1;

}

intcommstr(char)*str1,char *str2,int *sublen

{char*s1,*s2；

int count=0,len1,len2,k,j,i,p;

len1=strlen(str1);

len2=strlen(str2);

if(len1>len2)

{s1=str1;s2=str2;}

else{len2=len1;s1=str2;s2=str1;}

for(j=len2;j>0;j--)/*从可能最长子串开始寻找*

{for(k=0; (1) <=len2;k++)/*k为子串s2的开始位置*/

{for(i=0;s1［ (2) ］!='＼0';i++;)/* i为子串s1的开始位置*/

{/* s1的子串与s2的子串比较*/

for(p=0;p<j)&& (3) ;p++);

if ( (4) )/*如果两子串相同*/

{for(p=0);p<j;p++}/*输出子串*/

printf("%c",s2［k+p］);

printf("＼n");

count++；/* 计数增1*/

}

}

}

if (count>0)break;

*sublen=(count>0)? (5) :0;

return count;

}

写一个在一个字符串(n)中寻找一个子串(m)第

一个位置的函数。

阅读以下程序说明和C程序，将应填入(n)处的子句，写在对应栏内。

【程序说明】

函数int commstr(char * str1，char * str2，int * sublen)从两已知字符串str1和str2中，找出它们的所有最长的公共子串。如果最长公共子串不止1个，函数将把它们全部找出并输出。约定空串不作为公共子串。

函数将最长公共子串的长度送入由参数sublen所指的变量中，并返回字符串str1和str2的最长公共子串的个数。如果字符串str1和str2没有公共子串，约定最长公共子串的个数和最长公共子串的长度均为0。

【程序】

int strlen(char * s)

{char *t=s;

while( * ++);

return t-s-1;

}

int commstr(char) *str1,char *str2,int *sublen

{ char*s1, *s2;

int count=0,len1 ,len2,k,j,i,p;

len1:=strlen(str1)

len2 = strlen(str2);

if(len1＞len2)

{s1=str1 ;s2=str2;}

else {len2 = len1;s1 = str2;s2 = str1;}

for(j=len2;j＞0;j--) /*从可能最长子串开始寻找*/

{for(k=0;(1)＜:len2;k++) /*k为子串s2的开始位置*/

{for(i=0;s1[(2)]!='\0';i++;) /*i为子串s1的开始位置*/

{ /*s1的子串与s2的子串比较*/

for (p=0;p＜j)&&(3);p++);

if ((4)) /*如果两子串相同*/

{for(p=0);p＜j;p++} /*输出子串*/

printf ("%c",s2[k+p]);

printf ("\n");

count++;/*计数增1 */

}

}

}

if (count＞0) break;

*sublen=(count＞0)?(5):0;

return count;

}

A、0

B、2

C、3

D、5

阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。

【说明】

下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)组成，串B由m个字符B(0)，B(1)，…，B(m-1)组成，其中n≥m＞0。在串A中查找串 B的基本算法如下：从串A的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较；若不同，则再取子串A(1)A(2)…A(m)与串B比较，依次类推。

例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。

在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B中的字符(j=0，1，…，m-1)。在比较A(i)A(i/1)…A(i+m-1)与B(0)B(1)…B(m-1)时，需要对 A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。

【流程图】

A、联接

B、求子串

C、字符定位

D、子串定位

A、连接

B、求串长

C、串比较

D、子串定位

E、串复制

若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

A．O(1)

B．O(n)

C．O(n2)

D．0(n3)