AcWing 1285. 单词 题解（AC自动机）

AcWing 1285. 单词
用f记录一个与这个后缀相同的单词前缀出现的次数（不仅仅是单词出现的次数）

#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] ++ ;  //记录前驱出现的次数 
	}
	id[x] = p;  //每个单词被赋予一个编号 
}

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]];  //沿拓扑序倒序向上，将所有前驱节点的值累加到后继节点上 
	}
	
	for(int i = 0; i < n; i ++ ){
      
		cout<<f[id[i]]<<endl;
	}
	return 0;
}