显示代码纯文本
/*
子任务 1
条件：N<=100，时间复杂度为O(N^5)
思路:
对于这个问题，我们可以对每一对(K,L)应用暴力解法来模拟题目描述的过程。
我们可以遍历所有长度为K的子串，
并在其中找出所有长度为K的子串中的字典序最小的子串。
然后我们可以统计唯一 “获胜” 基因位置的数量，
并将其添加到一个更大的数组中。
注意，虽然这种暴力解法的时间复杂度是O(N^5)，
但是由于K和L的限制以及给定时有效子串的数量，
存在一个较小的分数常数因子，所以当N=100时，
在时间限制内可以轻松运行。
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("winninggene.in","r",stdin);
freopen("winninggene.out","w",stdout);
int N;
cin >> N; string S; cin >> S;
vector<int> cnt(N + 1, 0);
for (int K = 1; K <= N; ++K) {
for (int L = K; L <= N; ++L) {
vector<bool> marked(N, false);
for (int i = 0; i <= N - L; ++i) {
string best;
int best_idx = -1;
for (int j = i; j <= i + L - K; ++j) {
string current = S.substr(j, K);
if (best.empty() || current < best) {
best = current;
best_idx = j;
}
}
marked[best_idx] = true;
}
cnt[count(marked.begin(), marked.end(), true)] += 1;
}
}
for (int v = 1; v <= N; ++v)cout << cnt[v] << endl;
return 0;
}
yuan