3776 - 【START】2015暑期训练——字串统计
给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。
子串定义：串中任意个连续的字符组成的子序列称为该串的子串，对于一个字符串变量，例如"adereegfbw",它的子串就是像"ader"这样可以从中找到的连续的字符串。字符串"adereegfbw"本身也属于它本身最长的子串。
题目输入
第一行是一个整数M，表示输入数据的组数
记下来是M组数据
每组数据第一行一个数字L。
第二行是字符串S。
L大于0，且不超过S的长度。
题目输出
针对每组输入，输出一行，题目要求的字符串。以换行符结束。
输入/输出样例
题目输入
3 1 bbaabaaaaa 5 bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba 2 bbaabaaaaa
题目输出
a baabaa aa
C++解答
#include <iostream> #include <string> #include <cstdio> using namespace std; bool isSubStr(const std::string& str, int index1, int index2, int len) { for (int i(0); i != len; ++i) { if (str[index1 + i] != str[index2 + i]) return false; } return true; } // 在串中找以index开始，长度为len的串的数量 int repeat(const std::string& str, int index, int len) { int rep(1); for (unsigned i(index + 1); i <= str.size() - len; ++i) { if (isSubStr(str, index, i, len)) ++rep; } return rep; } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int L; string S; int M; cin >> M; while(M--) { cin >> L >> S; int maxRep(0), maxIndex(0), maxLen(0); // 子串长度 for (int len(S.size() - 1); len != L-1; --len) { for (unsigned i(0); i != S.size() - len; ++i) { // 从当前下标开始, len长度的子串 int rep = repeat(S, i, len); if (maxRep < rep) { maxRep = rep; maxIndex = i; maxLen = len; } } } cout << S.substr(maxIndex, maxLen); cout << endl; } return 0; }