You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
54 lines
1.1 KiB
54 lines
1.1 KiB
#include<iostream>
|
|
#include<string>
|
|
#include<vector>
|
|
using namespace std;
|
|
pair<int, string> fun(const string &str)
|
|
{
|
|
vector<string> substrs;
|
|
int len = str.length();
|
|
string substring;
|
|
int maxcount(0);
|
|
//后缀数组
|
|
for (int i = 0; i < len; ++i)
|
|
{
|
|
substrs.push_back(str.substr(i));
|
|
// cout << substrs[i] << endl;
|
|
}
|
|
for (int i = 0; i < len; ++i)
|
|
{
|
|
for (int j = 1; j <= len; j++) {
|
|
int count = 1;
|
|
int sublen = j;
|
|
for (int k = i + 1; k < len; k++) {
|
|
|
|
if (substrs[k].length() < sublen) {
|
|
break;
|
|
}
|
|
string str1 = substrs[i].substr(0, sublen);
|
|
string str2 = substrs[k].substr(0, sublen);
|
|
if (str1.compare(str2)==0)
|
|
{
|
|
++count;
|
|
}
|
|
}
|
|
if (count > maxcount||(count == maxcount && sublen > substring.length()))
|
|
{
|
|
maxcount = count;
|
|
substring = substrs[i].substr(0, sublen);
|
|
}
|
|
}
|
|
}
|
|
return make_pair(maxcount, substring);
|
|
}
|
|
|
|
int main()
|
|
{
|
|
string str;
|
|
int len;
|
|
cin >> len;
|
|
cin >> str;
|
|
auto res = fun(str);
|
|
cout << res.first << endl;
|
|
// cout << "the matched substring is:" << res.second << endl;
|
|
return 0;
|
|
}
|