1 #include"iostream" 2 #include"string" 3 #include"string.h" 4 #include"vector" 5 #include"algorithm" 6 using namespace std; 7 8 vector<string> subStr; 9 10 void GetSubStr(string str) 11 { 12 subStr.clear(); 13 for(int i=0;i<str.length();i++) 14 { 15 subStr.push_back(str.substr(i,str.length()-i)); 16 } 17 sort(subStr.begin(),subStr.end()); 18 // for(int i=0;i<str.length();i++) 19 // cout<<subStr[i]<<endl; 20 } 21 22 int CommonHead(string str1,string str2) 23 { 24 int i=0,j=0,len=0; 25 while(i<str1.length()&&j<str2.length()) 26 { 27 if(str1[i++]==str2[j++]) 28 len++; 29 else 30 break; 31 } 32 return len; 33 } 34 35 pair<string,int> GetRes(int length) 36 { 37 int resLen=0,resIndex=-1,tempLen; 38 string resSub; 39 for(int i=0;i<subStr.size()-1;i++) 40 { 41 tempLen=CommonHead(subStr[i],subStr[i+1]); 42 if(tempLen>resLen) 43 { 44 resLen=tempLen; 45 resIndex=length-max(subStr[i].length(),subStr[i+1].length())+1; 46 resSub=subStr[i].substr(0,resLen); 47 } 48 } 49 if(resIndex!=-1) 50 return make_pair(resSub,resIndex); 51 else 52 return make_pair("no answer",-1); 53 } 54 55 int main() 56 { 57 string src; 58 while(cin>>src) 59 { 60 GetSubStr(src); 61 pair<string,int> res=GetRes(src.length()); 62 cout<<res.first<<" "<<res.second<<endl; 63 } 64 return 0; 65 }
原文:https://www.cnblogs.com/acm-jing/p/10369575.html