社区讨论

if WA on #1

P3796AC 自动机(简单版 II)参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m3r511kg
此快照首次捕获于
2024/11/21 17:56
去年
此快照最后确认于
2025/11/04 14:15
4 个月前
查看原帖
可能是 query 函数写挂了,前面的帖子没有我这种挂法,放一下代码
C
ll query(char ch[], int len) {
  int nowp = 1; ll ret = 0;
  for (int i = 1; i <= len; i++) {
    while (!t[nowp].son[Int(ch[i])] && nowp > 1) nowp = t[nowp].fail;
    if (!t[nowp].son[Int(ch[i])]) continue;
    nowp = t[nowp].son[Int(ch[i])];
    //if (t[nowp].cnt) {
      int tmp = nowp;
      while (tmp > 1) {
        total[id[tmp]] += t[tmp].cnt;
        ret = std::max(ret, (ll)total[id[tmp]]);
        tmp = t[tmp].fail;
      }
    //}
  }
  return ret;
}

注释的这两行是我本来加的优化,但是假掉了,不一定要找到一个完整的模式串才向前递归查找。对于所有查到的点都要往前查是否有匹配字串,数据比较水,只在第一个点卡了。

回复

0 条回复,欢迎继续交流。

正在加载回复...