求助 - Trie树 80分
查看原帖
求助 - Trie树 80分
325319
ohnmachesya楼主2022/4/16 11:47

Trie树解法 80分

WA了 #1 和 #7 代码:

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

#define _ 2022
int trie[_][26] = {0};
int cnt = 0;
int vis[_] = {0};
int _cc = 0;
int maxc = -0x3f;
int n;

void insert(const string &s) {
	int cur = 1;
	for (auto c : s) {
		if (!trie[cur][c - 'a'])
			trie[cur][c - 'a'] = ++cnt;
		cur = trie[cur][c - 'a'];
	}
	vis[cur] = 1;
}
bool find(const string &s) {
	int cur = 1;
	for (auto c : s) {
		if (!trie[cur][c - 'a'])return false;
		cur = trie[cur][c - 'a'];
		if (vis[cur])_cc++;
	}
	return true;
}

int main() {
	string str[_];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> str[i];
		insert(str[i]);
	}
	for (int i = 1; i <= n; i++) {
		find(str[i]);
		maxc = max(maxc, _cc);
		_cc = -0x3f;
	}
	cout << maxc << endl;
}
2022/4/16 11:47
加载中...