AC自动机是一种算法，自动AC机是一种作弊工具
by Zyque @ 2019-05-25 18:48:35
不知问的是AC自动机还是自动AC机？
这两个看似只不过把词语换了个位置，但意思则大相径庭：一个是算法，一个是作弊工具。
AC自动机是著名的多模匹配算法，诞生于1975年的贝尔实验室。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符，当A[i+1]≠B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配，而next函数恰恰记录了这个j应该调整到的位置。同样AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Trie上进行匹配时，如果与当前节点的关键字不能继续匹配，就应该去当前节点的失败指针所指向的节点继续进行匹配。
AC自动机则是种高级算法，我所介绍的是种作弊方法。
这是一种非常玄学的东西，是用Pascal语言写的用来卡评测机的东西，卡软件BUG，以此来作弊使自己“AC”。
by Stephen_Curry @ 2019-05-25 18:57:59
@[Stephen_Curry](/space/show?uid=212267) ~~不容易啊，写这么多字~~
by SSerxhs @ 2019-05-25 19:01:28
@[Stephen_Curry](/space/show?uid=212267) 求自动AC机的原理
by zc_aha @ 2019-05-25 19:02:32
@[zc_aha](/space/show?uid=199359) 你想干什么……
by Celestial_Scarlet @ 2019-05-25 19:11:44
@[baoyu](/space/show?uid=93465) 好奇
~~我死也不会说要把它用在其他OJ上~~
by zc_aha @ 2019-05-25 19:17:29
@[zc_aha](/space/show?uid=199359) 自动AC机原理（题解大法
by 我不认识你 @ 2019-05-25 19:19:45
@[zc_aha](/space/show?uid=199359)
原理：
>自动AC机可以访问网络，在网络上搜索题目的题解，并逐一尝试是否AC。故自动AC机运行需要网络
by 蒟蒻lxy @ 2019-05-25 19:21:55
@[我不认识你](/space/show?uid=111380)
@[刘星宇0508](/space/show?uid=34500)
都是秀儿
by zc_aha @ 2019-05-25 19:44:19
@[zc_aha](/space/show?uid=199359)
一般是通过**特定OJ**的漏洞骗过评测机，产生直接AC的效果。（老实人
by 智子 @ 2019-05-25 20:10:52