阅读以下说明和流程图,填补流程图中空缺,将解答填入答题纸对应栏内。
[说明]
下面流程图功能是:在给定两个字符串中查找最长公共子串,输出该公共子串长度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两串没有公共子串。