#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <deque>
#include <list>
#include <cassert>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define pb push_back
#define mp make_pair
#ifdef GRAPH
typedef pair <int, int> Edge;
#define v first
#define w second
#endif
#define lsh(i) (1 << (i))
#define lshll(i) (1LL << (i))
#define rep(i, n) for (int (i) = 0; (i) < n; (i)++)
#define until(x) while (!x)
#define fail(s) assert(!s)
const int INF = 0x3f3f3f3f;
const long double EPS = 1e-6;
const int N = 1010, C = 27;
struct TrieNode {
	int dest[C];
	int terminate;
	TrieNode() {
		memset(dest, 0, sizeof(dest));
		terminate = 0;
	}
};
TrieNode Trie[90 * N];
int root = 0, tot = 1;
void TrieInsert(string s, int xx) {
	int x = root;
	for (int i = 0; i < (int)s.length(); i++) {
		int p = s[i] - 'a';
		if (!Trie[x].dest[p])Trie[x].dest[p] = ++tot;
		x = Trie[x].dest[p];
	}
	Trie[x].terminate = xx;
}
int TrieFind(string s) {
	int x = root;
	for (int i = 0; i < (int)s.length(); i++) {
		int p = s[i] - 'a';
		if (!Trie[x].dest[p])return -1;
		x = Trie[x].dest[p];
	}
	return Trie[x].terminate;
}
int n;
string start;
string s[N];
int vis[N]; 
vector <int> G[N];
void BFS() {
	queue <int> q;
	q.push(0);
	vis[0] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (vector <int> :: iterator it = G[u].begin(); it != G[u].end(); it++) {
			int v = *it;
			if (vis[v]) continue;
			vis[v] = true;
			q.push(v);
		} 
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> start;
	TrieInsert(start, 0);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		if (s[i].length() > 3)
			TrieInsert(s[i], i);
	}
	for (int i = 1; i <= n; i++) {
		string now = s[i];
		for (int j = 0; j < (int)now.length(); j++) {
			now.erase(now.begin() + j);
			cerr << now << endl;
			int x = TrieFind(now);
			if (x != -1) {
				G[x].pb(i);
				cerr << x << ' ' << i << endl; 
			} 
			now = s[i];
		}
	}
	BFS();
	int besti = 0, bestv = -1;
	for (int i = 0; i <= n; i++) {
		if (vis[i] == 1 && ((int)s[i].length() > bestv)) {
			bestv = s[i].length();
			besti = i;
		}
	} 
	cout << s[besti] << endl;
	return 0;
}

• Re:求助：Trie树WA了 (2714) ravenclaw 2019-08-14 20:20:05