第7、8、9、10、11点TLE,数据泰大了。(样例全过)
查看原帖
第7、8、9、10、11点TLE,数据泰大了。(样例全过)
564997
Sad_bee_楼主2023/5/28 10:13
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 160, MAXL = 1e6;

char t[MAXL], p[N][80];
int sum[N], id[N];
vector<int> ans;

bool cmp(int a, int b) {
    if (sum[a] != sum[b]) return sum[a] > sum[b];
    return a < b;
}

int kmp(char a[], char b[]) {
    int n = strlen(a + 1), m = strlen(b + 1), j = 0;
    int f[N];
    f[1] = 0;
    for (int i = 2; i <= m; i++) {
        while (j && b[i] != b[j + 1]) j = f[j];
        if (b[i] == b[j + 1]) j++;
        f[i] = j;
    }
    j = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        while (j && a[i] != b[j + 1]) j = f[j];
        if (a[i] == b[j + 1]) j++;
        if (j == m) { res++; j = f[j]; }
    }
    return res;
}

int main() {
    int n;
    while (scanf("%d", &n), n) {
        memset(sum, 0, sizeof sum);
        for (int i = 0; i < n; i++) {
            scanf("%s", p[i] + 1);
        }
        scanf("%s", t + 1);
        int m = strlen(t + 1);
        for (int i = 0; i < n; i++) {
            sum[i] = kmp(t, p[i]);
            id[i] = i;
        }
        ans.clear();
        sort(id, id + n, cmp);
        ans.push_back(id[0]);
        int maxn = sum[id[0]];
        for (int i = 1; i < n && sum[id[i]] == maxn; i++) {
            ans.push_back(id[i]);
        }
        sort(ans.begin(), ans.end());
        printf("%d\n", maxn);
        for (int i = 0; i < ans.size(); i++) printf("%s\n", p[ans[i]] + 1);
    }
    return 0;
}
2023/5/28 10:13
加载中...