网站建设前期费用,办公室设计装修咨询,做搜狗网站,用wordpress建wiki正题
ybtoj AC自动机-3 题目大意
给你一个字符串和若干匹配串#xff0c;问你匹配串的前缀和字符串的最大匹配 解题思路
先把所有匹配串丢进AC自动机#xff0c;然后拿字符串去跑
每次只在当前位置存下贡献#xff0c;然后按bfs的倒叙传递贡献#xff0c;最后再倒着跑每…正题
ybtoj AC自动机-3 题目大意
给你一个字符串和若干匹配串问你匹配串的前缀和字符串的最大匹配 解题思路
先把所有匹配串丢进AC自动机然后拿字符串去跑
每次只在当前位置存下贡献然后按bfs的倒叙传递贡献最后再倒着跑每个匹配串 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 10000010
using namespace std;
int n, w, hd, tl, len, q[N], b[N], d[N], v[N], nx[N], fa[N], to[N][4];
char s[N], ss[N];
int check(char g)
{if (g E) return 0;if (g S) return 1;if (g W) return 2;if (g N) return 3;
}
int insert(char* s)
{int now 0, n strlen(s1);for (int i 1; i n; i){int y check(s[i]);if (!to[now][y]) to[now][y] w;fa[to[now][y]] now;q[to[now][y]] q[now] 1;now to[now][y];}return now;
}
void bfs()
{for (int i 0; i 4; i)if (to[0][i]) d[tl] to[0][i];while(hd tl){int h d[hd];for (int i 0; i 4; 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;
}
void ask(char* s)
{int now 0;for (int i 1; i len; i){int y check(s[i]);now to[now][y];b[now] 1;}return;
}
int find(int x)//倒着跑匹配串
{while(x !b[x]) x fa[x];return q[x];
}
int main()
{scanf(%d%d, len, n);scanf(%s, ss1);for (int i 1; i n; i){scanf(%s, s1);v[i] insert(s);}bfs();ask(ss);for (int i tl; i 0; --i)b[nx[d[i]]] | b[d[i]];//传递贡献for (int i 1; i n; i)printf(%d\n, find(v[i]));return 0;
}
