阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如,字符串"The light is not bright tonight"与"Tonight the light is not bright"的最长公共子串为"he light is not bright",长度为22,起始位置分别为2和10。
设A[1:M]表示由M个字符A[1],A[2],…,A[M]依次组成的字符串;B[1:N]表示由N个字符B[1],B[2],…,B[N]依次组成的字符串,M≥N≥1。
本流程图采用的算法是:从最大可能的公共子串长度值开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串,即在A、B字符串中分别顺序取出长度为L的子串后,调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
[流程图]
正确答案及解析
正确答案
解析
N或rnin(M,N)
M-L+1
N-L+1
L-1
L,I,J
【解析】
本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。
本题的算法可用来检查某论文是否有大段抄袭了另一论文。"The light is not bright tonight"是著名的英语绕口令,它与"Tonight the light is not bright"大同小异。
由于字符串A和B的长度分别为M和N,而且M≥N≥1,所以它们的公共子串长度L必然小于或等于N。题中采用的算法是,从最大可能的公共子串长度值L开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串。因此,初始时,应将min(M,N)送L,或直接将N送L。(1)处应填写N或min(M,N),或其他等价形式。
对每个可能的L值,为查看A、B串中是否存在长度为L的公共子串,显然需要执行双重循环。A串中,长度为L的子串起始下标可以从l开始直到M-L+1(可以用实例来检查其正确性);B串中,长度为L的子串起始下标可以从1开始直到N-L+1。因此双重循环的始值和终值就可以这样确定,即(2)处应填M-L+1,或等价形式;(3)处应填N-L+1或等价形式(注意循环的终值应是最右端子串的下标起始值)。
A串中从下标I开始长度为L的子串可以描述为A[I:I+L-1];B串中从下标J开始长度为L的子串可以描述为A[J:J+L-1]。因此,双重循环体内,需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。
如果这两个子串比较的结果相同,那么就已经发现了A、B串中最大长度为L的公共子串,此时,应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起始下标J。因此,(5)处应填L,I,J(可不计顺序)。
如果这两个子串比较的结果不匹配,那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时,就需要将L减少1((4)处填L-1或其等价形式)。只要L非0,则还可以继续对新的L值执行双重循环。如果直到L=0,仍没有发现子串匹配,则表示A、B两串没有公共子串。
你可能感兴趣的试题
一台主机的IP地址为202.123.25.36,掩码为255.255.254.0。如果该主机需要在该网络进行直接广播,那么它应该使用的目的地址为( )
-
- A.202.123.25.0
- B.202.123.25.255
- C.202.123.24.0
- D.202.123.24.255
- 查看答案
在计算机系统的日常维护工作中,应当注意硬盘工作时不能__(2)__。另外,需要防范病毒,而__(3)__是不会被病毒感觉的。
-
- A.电子邮件
- B.硬盘
- C.U盘
- D.ROM
- 查看答案
有 4 个 IP 地址:201.117.15.254、201.117.17.01、201.117.24.5 和 201.117.29.3,如果子网掩码为 255.255.248.0,则这 4 个地址分别属于3个子网;其中属于同一个子网的是()
-
- A.201.117.15.254 和 201.117.17.01
- B.201.117.17.01 和 201.117.24.5
- C.201.117.15.254 和 201.117.29.3
- D.201.117.24.5 和 201.117.29.3
- 查看答案
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位,每秒钟传送200个字符,采用4相位调制,则码元速率为()。
-
- A.50波特
- B.500波特
- C.550波特
- D.1000波特
- 查看答案
在 Windows 中,运行( )命令得到下图所示结果。以下关于该结果的叙述中,错误的是( )。
Pinging 59.74.111.8 with 32 bytes of data:
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Ping statistics for 59.74.111.8:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 3ms, Maximum = 5ms, Average = 4ms
-
- A.该命令使得本地主机向目标主机发送了 4 个数据包
- B.本地主机成功收到了目标主机返回的 4 个数据包
- C.本地主机与目标主机连接正常
- D.该命令用于查看目标主机的 IP 地址
- 查看答案