问题 5165 --云卓公共字符串

5165: 云卓公共字符串★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 197  解决: 65
[提交][状态][命题人:]

题目描述

云卓在昨天的杭州市编程比赛中,一鸣惊人,不仅得了满分,而且获得了“天王星”的光荣称号。

这下更激发了他学习编程的潜能,他每天会选一个问题进行深入钻研,今天他就打算来钻研一下最长公共字符串问题。

求字符环上的最长公共字符串:将字符串首尾相接后可以得到一个字符环,如图a和图b所示(张博士手动画的,将就看吧),分别为由字符串sunlight's和sunshine's首尾相接后得到的环,它们的最长的公共字符串为'ssun,长度为5。编写程序实现如下功能:输入两个字符环,输出其最长公共字符串和长度。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int len1=s1.length();
	int len2=s2.length();
	int minlen=len1;
	if (len2<len1) 
		______(1)_______;
	string common="";
	int c1=0;
	for(int i=0;i<len1;i++)
		for(int j=0;j<len2;j++)
		{
			int temp=0,itemp=i,jtemp=j;
			while(s1[itemp]==s2[jtemp] && temp<minlen)
			{
				temp++;
				itemp=______(2)_______;
				jtemp=______(3)_______;
				if (temp>c1)
				{
					c1=temp;
					if(i<itemp)
						common=______(4)_________;
					else
						common=______(5)_________;
				}
			}
		}
	cout<<common<<endl;
	cout<<c1<<endl;
}

输入

输出

1) 第1空的答案为________ 
A. minlen=len2   B. len1=len2    C. minlen=len1    D. len2=len1

2) 第2空的答案为________ 
A. itemp+1   B. itemp%len1    C. (itemp+1)%len1    D. (itemp+len1)%len1

3) 第3空的答案为________ 
A. jtemp+1   B. jtemp%len2    C. (jtemp+1)%len2    D. (jtemp+len2)%len2

4) 第4空的答案为________ 
A. s1.substr(itemp-i)   B. s1.substr(i)    C. s1.substr(i,itemp)    D. s1.substr(i,itemp-i)

5) 第5空的答案为________ 
A. s1.substr(i)+s1.substr(0,itemp-1)   B. s1.substr(i)+s1.substr(1,itemp)    C. s1.substr(i)+s1.substr(0,itemp)    D. s1.substr(i)+s1.substr(itemp)

6)如果输入的两个字符串分别为"zhangyongliang"和"litanghong",则输出的答案为________
A. ong      B. ang     C. liong    D. ongli
   3           3          5           5

提示

只需输出选项答案,每行一个大写字母,一共6行

来源

[提交][状态]