分析：首先生成后缀数组
1 //求一个字符串中连续出现次数最多的子串
2
3 #include "stdafx.h"
4 #include <iostream>
5 #include <vector>
6 #include <string>
7 using namespace std;
8
9 pair<int,string> fun(const string &str)
10 {
11 vector<string> subStrs;
12 int maxcount=1,count=1;
13 string subStr;
14 int i,len=str.length();
15 for(i=0;i<len;i++) //生成后缀数组
16 subStrs.push_back(str.substr(i,len-i));
17 for(i=0;i<len;i++)
18 {
19 for(int j=i+1;j<len;j++)
20 {
21 count=1;
22 if(subStrs[i].substr(0,j-i)==subStrs[j].substr(0,j-i))
23 {
24 ++count;
25 for(int k=j+(j-i);k<len;k+=j-i)//间隔(j-i)个字母后，看是否重复出现，重复出现则连续
26 {
27 if(subStrs[i].substr(0,j-i)==subStrs[k].substr(0,j-i))
28 ++count;
29 else
30 break;
31 }
32 if(count>maxcount)
33 {
34 maxcount=count;
35 subStr=subStrs[i].substr(0,j-i);
36 }
37 }
38 }
39 }
40 return make_pair(maxcount,subStr);
41
42 }
43
44
45 int _tmain(int argc, _TCHAR* argv[])
46 {
47 string str;
48 pair<int,string> rs;
49 while(cin>>str)
50 {
51 rs=fun(str);
52 cout<<rs.second<<":"<<rs.first<<"\n";
53 }
54 return 0;
55 }
然后再逐渐缩小字符子串来得出正确的结果
subStrs[0]比subStrs[1]多了一个字母,如果说存在连续匹配的字符,那么
subStrs[0]的第1个字母要跟subStrs[1]首字母匹配,同理
subStrs[0]的前2个字母要跟subStrs[2]的前2个字母匹配(否则不能叫连续匹配)
subStrs[0]的前n个字母要跟subStrs[n]的前n个字母匹配.
如果匹配的并记下匹配次数.如此可以求得最长连续匹配子串.