首页 > 其他 > 详细

面试宝典——找出一个字符串中最长公共子串

时间:2019-02-13 15:05:50      阅读:237      评论:0      收藏:0      [点我收藏+]
技术分享图片
 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 }
View Code

 

面试宝典——找出一个字符串中最长公共子串

原文:https://www.cnblogs.com/acm-jing/p/10369575.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!