云卓在昨天的杭州市编程比赛中,一鸣惊人,不仅得了满分,而且获得了“天王星”的光荣称号。
这下更激发了他学习编程的潜能,他每天会选一个问题进行深入钻研,今天他就打算来钻研一下最长公共字符串问题。
求字符环上的最长公共字符串:将字符串首尾相接后可以得到一个字符环,如图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; }