学网站建设的好处,舟山外贸建站公司,主流网站风格,国内公司网站需要备案解析 我对力量一无所知 通过这题#xff0c;可以看出我对AC自动机还是完全没有理解 qwq 首先容易想到#xff1a; 建一课trie树#xff0c;然后建树时记录每个串s的终点#xff0c;这个点后面每被经过一次#xff0c;就相当于出现一次该单词s 但是#xff0c;这种“出现”…
解析 我对力量一无所知 通过这题可以看出我对AC自动机还是完全没有理解 qwq 首先容易想到 建一课trie树然后建树时记录每个串s的终点这个点后面每被经过一次就相当于出现一次该单词s 但是这种“出现”只是当s恰好是后面的前缀时才会被计算 所以我们想到其实到这我就没想到 任何一个以s为后缀的结点被遍历到时s都会出现一次 同时我们发现这样统计可以做到不重不漏 所以我们就可以写出一个不伦不类的方程 ans[s]∑ans [s1] (s是s1的后缀) 然后利用AC自动机的机制类似前缀和一样的滚起来就可以解决本题 另外值得注意的一点是AC自动机bfs之后用完的那个队列中恰好是按bfs排列的废话 转移时我们可以直接利用
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N1e6100;
int tr[N][27],tot1;
int n;
char s[N];
int cnt0;
int k,id[N];
int num[N];
void build(){int lstrlen(s1),pl1;for(int i1;il;i){int as[i]-a1;if(!tr[pl][a]) tr[pl][a]tot;pltr[pl][a];num[pl];}id[k]pl;//num[pl];
}
int q[N],st,ed,nxt[N];
void bfs(){stedq[1]1;for(int i1;i26;i) tr[0][i]1;nxt[1]0;while(sted){int nowq[st];for(int i1;i26;i){if(!tr[now][i]) tr[now][i]tr[nxt[now]][i];else{q[ed]tr[now][i];nxt[tr[now][i]]tr[nxt[now]][i];}}}for(int ied;i1;i--){num[nxt[q[i]]]num[q[i]];}return;
}int main() {scanf(%d,n);for(int i1;in;i){scanf(%s,s1);ki;build();}bfs();for(int i1;in;i){printf(%d\n,num[id[i]]);}return 0;
}/*
3
a
aa
aaa
*/
