if WA on #1
查看原帖
if WA on #1
689507
liu_he_yong楼主2024/11/21 17:56

可能是 query 函数写挂了,前面的帖子没有我这种挂法,放一下代码

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;
}

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

2024/11/21 17:56
加载中...