题目内容
（请给出正确答案）
假设允许模式串p中可以出现能与任意字符串(包括长度为0的空串)匹配的回隙字符 ,如模式串ab
bac可在主串cabccbacbacab中产生如图9-3所示的匹配.间隙字符可在模式串中出现任意多次,但不允许在主串中出现.
试设计一个多项式时间算法,确定在主串中能否找到与模式串p匹配的子串,并分析算法的计算时间复杂性.
如果结果不匹配，请 联系老师 获取答案
更多“假设允许模式串p中可以出现能与任意字符串（包括长度为0的空串…”相关的问题
设有两个字符串p和q，求q在p中首次出现位置的运算称为（）。
A.连接
B.模式匹配
C.求子串
D.求串长
（58）A. 0123123
B. 0123210
C. 0123432
D. 0123456
求字符串T在字符串S中首次出现的位置称为(42)。
A．串的模式匹配
B．求子串
C．求串的长度
D．串的连接
下列给定程序中，函数fun()的功能是：在字符串的最前端加入n个*号，形成新串，并且覆盖原串。
注意：字符串的长度最长允许79。
请改正函数fun()中的错误，使它能得出正确的结果。
注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。
试题程序；
include ＜stdio.h＞
include ＜strzng.h＞
include ＜conio.h＞
/*****************found***************/
void fun(char s[], int n)
{
char a[80]，*p；
int i;
/*****************found***************/
s=p;
for(i=0; i＜n; i++) a[i]='*'；
do
{a[i]=*p；
/*****************found***************/
i++;
}while(*p)；
a[i]=0；
strcpy(s,a)；
}
main()
{ int n;char s[80]；
clrscr()；
printf("\nEnter a string:");gets(s);
printf("\nThe string\%s\n",s);
printf("\nEnter n(number of*):");scanf ("%d"，&n);
fun(s,n)；
printf("\nThe string after inster: \%s\n",s)；
}
以下关于字符串的叙述中，正确的是（）。
A.包含任意个空格字符的字符串称为空串B. 字符串不是线性数据结构C. 字符串的长度是指串中所含字符的个数D. 字符串的长度是指串中所含非空格字符的个数
没有两个串p和q,求q在p首次出现位置的运算称作
A．连接
B．模式匹配
C．求于串
D．求串长
在匹配器(Matcher)类中，用于输入字符串与模式串比较的方法是
A．static boolean matches()
B．boolean matcher,find()
C．int matcher,start()
D．int matcher,end()
在匹配器(Matcher)类中，用于输入字符串与模式串比较的方法是()。
A．static boolean matches()
B．boolean matcher.find()
C．int matcher.start()
D．int matcher.end()
在图9-2(a)中匹配失败后,按前缀函数指示继续作了图(b)~(d)的比较后,最后在图(e)找到一个匹配.事实上,图(b)~(d)的比较都是多余的.因为模式串在位置0、1、2处的字符和位置3处的字符都相等,因此不需要再和主串中位置3处的字符比较,而可以将模式一次向右滑动4个字符,直接进入图(e)的比较.这就是说,在KMP算法中遇到p[j+1]≠t[i],且p[j+1]=p[next[j]+1]时,可一次向右滑动j-next[next[j]]个字符,而不是j-next[j]个字符.根据此观察,设计一个改进的前缀函数,使得遇到上述特殊情况时效率更高.
