这题跟洛谷模板的加强版啥区别
查看原帖
这题跟洛谷模板的加强版啥区别
469309
凤年楼主2023/5/18 20:36

rt,题目样例都一样,代码交上去就WA

#include <bits/stdc++.h>
using namespace std;

int n;
string s, str;

int tot = 0;
string ask[153];
int fail[10510], cnt[10510], trie[10510][26];

map<string, int> mp;

void clear() {
	tot = 0;
	mp.clear();
	memset(cnt, 0, sizeof(cnt));
	memset(fail, 0, sizeof(fail));
	memset(trie, 0, sizeof(trie));
}
void add(string s) {
	int p = 0, len = s.size();
	for(int i = 0; i < len; ++i) {
		int num = s[i] - 'a';
		if(!trie[p][num]) trie[p][num] = ++tot;
		p = trie[p][num];
	}
	cnt[p] = len; //根节点到 p 点的长度即单词长度
}
void getFail() {
	queue<int> q;
	fail[0] = 0;
	for(int i = 0; i < 26; ++i) {
		if(trie[0][i]) {
			fail[trie[0][i]] = 0;
			q.push(trie[0][i]);
		}
	}
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		for(int i = 0; i < 26; ++i) {
			if(trie[now][i]) {
				fail[trie[now][i]] = trie[fail[now]][i];
				q.push(trie[now][i]);
			} else {
				trie[now][i] = trie[fail[now]][i];
			}
		}
	}
}
void query(string s) {
    int now = 0, ans = -1;
	for(int i = 0, len = s.size(); i < len; ++i) {
		now = trie[now][s[i] - 'a'];
		for(int j = now; j && cnt[j] != -1; j = fail[j]) {
			if(cnt[j])
				++mp[s.substr(i - cnt[j] + 1, cnt[j])];
		}
	}
	for(auto it = mp.begin(); it != mp.end(); ++it)
		ans = max(ans, it->second);
    printf("%d\n", ans);
    for(int i = 1;i <= n; ++i)
        if(mp[ask[i]] == ans)
            cout << ask[i] << endl;
}
int main() {
	while(1) {
		cin >> n;
		if(n == 0) return 0;
		clear();
		for(int i = 1; i <= n; ++i) {
			cin >> ask[i];
			add(ask[i]);
		}
		getFail();
		cin >> str;
		query(str);
	}
	return 0;
}
2023/5/18 20:36
加载中...