pos sin algo cstring n) -s 丢失 oid 一个
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3172
对这$n$个串建立AC自动机,求每个串的出现次数。
我们在建立时对每一个经过的节点sum++,然后在fail树上从叶子节点不断向上更新,因为父亲节点代表的是孩子节点的一个后缀,所以孩子出现过的父亲一定出现过,而fail指针的不遗漏性保证了答案不会丢失。
- #include < cstdio > #include < cstring > #include < algorithm > using namespace std;
- int N,
- ch[1000010][26],
- fail[1000010],
- cnt = 0;
- int sum[1000010],
- pos[1000010];
- char tmp[1000010];
- int Insert(char * s) {
- int now = 0;
- for (int i = 0; s[i]; i++) {
- int idx = s[i] - ‘a‘;
- if (!ch[now][idx]) ch[now][idx] = ++cnt;
- now = ch[now][idx];
- sum[now]++;
- }
- return now;
- }
- int q[1000010];
- void Setfail() {
- q[1] = 0;
- int head = 1,
- tail = 1;
- while (head <= tail) {
- int now = q[head];
- for (int i = 0; i < 26; i++) {
- if (ch[now][i]) {
- q[++tail] = ch[now][i];
- fail[ch[now][i]] = now ? ch[fail[now]][i] : 0;
- } else ch[now][i] = ch[fail[now]][i];
- }
- head++;
- }
- for (int i = tail; i >= 1; i--) sum[fail[q[i]]] += sum[q[i]];
- }
- int main() {
- scanf("%d", &N);
- for (int i = 1; i <= N; i++) {
- scanf("%s", tmp);
- pos[i] = Insert(tmp);
- }
- Setfail();
- for (int i = 1; i <= N; i++) printf("%d\n", sum[pos[i]]);
- return 0;
- }
[BZOJ3172][TJOI2013]单词 AC自动机
来源: http://www.bubuko.com/infodetail-2340680.html