要跳的吧,跳 fail 相当于砍掉当前匹配字符串的一段前缀,可能砍完以后就匹配上了一个很小的串
by yukimianyan @ 2024-02-22 15:38:27
@[huangziqin](/user/185223) 为什么不用跳 fail
by OldDriverTree @ 2024-02-22 15:38:43
```
now=0;
for(int i=0;i<s.size();i++)
{
int sn=tr[now][s[i]-'a'];
now=tr[now][s[i]-'a'];
f[now]=1;
}
```
我的意思是查询的时候这样子匹配
by huangziqin @ 2024-02-22 15:39:45
```
for(int i=0;i<26;i++)
{
if(tr[ou][i])
{
fail[tr[ou][i]]=tr[ff][i]; q.push(tr[ou][i]);
}
else tr[ou][i]=tr[ff][i];
}
```
因为注意到前面的else那一句,其实和跳fail是一样的意思
而且这么写是可以过板子的
by huangziqin @ 2024-02-22 15:40:40
@[OldDriverTree](/user/681036) @[yukimianyan](/user/509229)
by huangziqin @ 2024-02-22 15:40:52
你是说 `now=tr[now][s[i]-'a'];` 还是 `f[now]=1;` 要跳 fail,前面那个因为已经建出 trie 图所以不需要跳 fail,后面那个需要跳 fail,匹配到 fail 树上它到根的整条链
by yukimianyan @ 2024-02-22 15:41:06
@[yukimianyan](/user/509229) 前面那个 但是翻了一下题解,都有写一个while
抱歉是我没有说清楚
by huangziqin @ 2024-02-22 15:42:37
```
void pp()
{
now=0;
for(int i=0;i<s.size();i++)
{
int sn=tr[now][s[i]-'a'];
while(sn&&cnt[sn]!=-1)
{
ans+=cnt[sn]; cnt[sn]=-1; sn=fail[sn];
}
now=tr[now][s[i]-'a'];
}
return;
}
```
就是这种写法
by huangziqin @ 2024-02-22 15:43:36
这种写法是后面那个 `f[now]=1;` 跳了 fail
by yukimianyan @ 2024-02-22 15:46:10
@[yukimianyan](/user/509229) 有后面那一句
我真是奇了怪了
by huangziqin @ 2024-02-22 15:46:27