AcWing 1285. Word Problem Solving (AC Automata)

AcWing 1285. 单词
用fRecord a prefix and the suffix of the same word the number of occurrences of（Not only is the number of occurrences of words）

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int tr[N][26], f[N], q[N];
int n;
string str;
int ids;
int id[N];
int ne[N];

void insert(int x){
    
	int p = 0;
	for(int i = 0; str[i]; i ++ ){
    
		int t = str[i] - 'a';
		if(!tr[p][t]) tr[p][t] = ++ ids;
		p = tr[p][t];
		f[p] ++ ;  //The number of records precursors appear 
	}
	id[x] = p;  //Each word is assigned a number 
}

void build(){
    
	int hh = 0, tt = -1;
	for(int i = 0; i < 26; i ++ ){
    
		if(tr[0][i]) q[ ++ tt] = tr[0][i];
	}
	
	while(hh <= tt){
    
		int t = q[hh ++ ];
		for(int i = 0; i < 26; i ++ ){
    
			int &p = tr[t][i];
			if(!p) p = tr[ne[t]][i];
			else{
    
				ne[p] = tr[ne[t]][i];
				q[ ++ tt] = p;
			}
		}
	}
}

int main()
{
    
	cin>>n;
	for(int i = 0; i < n; i ++ ){
    
		cin>>str;
		insert(i);
	}
	
	build();
	
	for(int i = ids - 1; i >= 0; i -- ){
    
		f[ne[q[i]]] += f[q[i]];  //Along the topological sequence upward in reverse chronological order,All progressive values to subsequent precursor node 
	}
	
	for(int i = 0; i < n; i ++ ){
      
		cout<<f[id[i]]<<endl;
	}
	return 0;
}