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