做网站用什么主机好,宁波seo营销技巧,网络整合营销的优势,网站开发工程师薪酬待遇正题
luogu 3966 ybtoj AC自动机-2 题目大意
给你n个单词#xff0c;让你查询这写单词分别在这n个单词中出现过多少次 解题思路
先用AC自动机建好图#xff0c;然后每个点的权值为1#xff0c;然后向nx传递 代码
#includecstdio
#includecstring
#inclu…正题
luogu 3966 ybtoj AC自动机-2 题目大意
给你n个单词让你查询这写单词分别在这n个单词中出现过多少次 解题思路
先用AC自动机建好图然后每个点的权值为1然后向nx传递 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1000100
using namespace std;
int n, w, hd, tl, d[N], v[N], a[N], b[N], nx[N], to[N][30];
char s[N];
int insert(char* s)
{int n strlen(s1), now 0;for (int i 1; i n; i){int y s[i] - a;if (!to[now][y]) to[now][y] w;now to[now][y];b[now];//权值为1}return now;
}
void bfs()
{hd tl 0;for (int i 0; i 26; i)if (to[0][i]) d[tl] to[0][i];while(hd tl){int h d[hd];for (int i 0; i 26; i)if (!to[h][i]) to[h][i] to[nx[h]][i];else nx[to[h][i]] to[nx[h]][i], d[tl] to[h][i];}return;
}
int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%s, s1);v[i] insert(s);}bfs();for (int i tl; i 0; --i)//传递{int x d[i];a[x] b[x];b[nx[x]] b[x];}for (int i 1; i n; i)printf(%d\n, a[v[i]]);return 0;
}
