https://www.luogu.com.cn/record/159116838

想封装一下……

96分挂在第18个点，以为是递归深度问题，拿回去把fail树上DFS的递归（爆栈）改成拓扑排序之后，运行结果还是和标答差了十万八千里

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<vector>
#include<functional>
#include<deque>
#include<cmath>
using namespace std;
typedef pair<long long, long long> pii;
typedef vector<long long> vll;
typedef long long ll;
typedef long long i64;

//#define DEBUG

#ifdef DEBUG
const long long N = 1000;
#endif
#ifndef DEBUG
const long long N = 500100;
#endif
// const ll M = 998244353;
// YOUR CODE HERE
const int DICT_SIZE = 28;
inline const int encode(char c)
//Maps a character to one of the integers in [0, DICT_SIZE).
{
	return c-97;
}
// END
struct trieNode{
	int id, fail, match;
	bool terminal;
	int trans[DICT_SIZE];
	trieNode(){
	}
	trieNode(int x): id(x), fail(0), match(0), terminal(0){
		memset(trans, 0 , sizeof(trans));
	}
};

class ACAutomaton{
public:
	ACAutomaton();
	ACAutomaton(vector<string>&);
	vector<int> match(string);
private:
	vector<int> patternMap;
	vector<trieNode> dictGraph;
	void buildTrie(vector<string>&);
	void buildGraph();
	void buildTopo();
	vector<int> topoSort;
};

ACAutomaton::ACAutomaton(){
	patternMap.clear();
	topoSort.clear();
	dictGraph = {trieNode(0)};
}

ACAutomaton::ACAutomaton(vector<string>& patterns){
	patternMap.clear();
	dictGraph = {trieNode(0)};
	buildTrie(patterns);
	buildGraph();
	buildTopo();
}

void ACAutomaton::buildTrie(vector<string>& patterns){
	int cnt = 0;
	for(string pattern: patterns)
	{
		int cur = 0;
		for(char c: pattern)
		{
			int code = encode(c);
			if(dictGraph[cur].trans[code] == 0)
			{
				cnt++;
				dictGraph[cur].trans[code] = cnt;
				dictGraph.push_back(trieNode(cnt));
			}
			cur = dictGraph[cur].trans[code];
		}
		dictGraph[cur].terminal = 1;
		patternMap.push_back(cur);
	}
}

void ACAutomaton::buildGraph(){
	dictGraph[0].fail = 0;
	deque<int> bfs;
	for(int i=0; i<DICT_SIZE; i++) if(dictGraph[0].trans[i] != 0)
	{
		bfs.push_back(dictGraph[0].trans[i]);
		dictGraph[dictGraph[0].trans[i]].fail = 0;
	}
	while(!bfs.empty())
	{
		trieNode &cur = dictGraph[bfs.front()];
		bfs.pop_front();
		for(int i=0; i<DICT_SIZE; i++) if(cur.trans[i] != 0)
		{
			bfs.push_back(cur.trans[i]);
			dictGraph[cur.trans[i]].fail = dictGraph[cur.fail].trans[i];
		}
		else 
			cur.trans[i] = dictGraph[cur.fail].trans[i];

	}
}

void ACAutomaton::buildTopo()
{
	int m = dictGraph.size();
	vector<int> incoming(m, 0);
	for(int i=1; i<m; i++)
		incoming[dictGraph[i].fail] ++;
	for(int i=1; i<m; i++) if(incoming[i] == 0)
		topoSort.push_back(i);
	int tail = topoSort.size();
	int head = 0;
	for(; head!=tail; head++)
	{
		int target = dictGraph[topoSort[head]].fail;
		incoming[target] --;
		if(incoming[target] == 0)
		{
			topoSort.push_back(target);
			tail++;
		}
	}
}


vector<int> ACAutomaton::match(string text){
	int state = 0;
	for(trieNode i: dictGraph) i.match = 0;
	for(char c: text)
	{
		int code = encode(c);
		while(dictGraph[state].trans[code] == 0 && state != 0) 
		{
			state = dictGraph[state].fail;
			dictGraph[state].match ++;
		}
		state = dictGraph[state].trans[code];
		dictGraph[state].match ++;
	}
	for(int i:topoSort)
		dictGraph[dictGraph[i].fail].match += dictGraph[i].match;
	vector<int> ans;
	for(int i: patternMap)
		ans.push_back(dictGraph[i].match);
	return ans;
}

int main()
{
    #ifdef DEBUG
    freopen("1.txt", "r", stdin);
    freopen("2.txt", "w", stdout);
    #endif
    int z;
    z = 1;
    //cin >> z;
    while(z--){
		int n;
		scanf("%d", &n);
		vector<string> patterns;
		for(int i=0; i<n; i++)
		{
			string s;
			cin >> s;
			patterns.push_back(s);
		}	
		ACAutomaton solver(patterns);
		string text;
		cin >> text;
		
		vector<int> ans = solver.match(text);
		
		for(int i: ans) printf("%d\n", i);
    }
 	return 0;
}