2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza [2020/07/16 22:24] lgwza [第二个优化] |
2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza [2020/07/16 22:24] (当前版本) lgwza [统计每个前缀的出现次数] |
||
|---|---|---|---|
| 行 159: | 行 159: | ||
| ==== 统计每个前缀的出现次数 ==== | ==== 统计每个前缀的出现次数 ==== | ||
| - | 在该节我们将同时讨论两个问题。给定一个长度为 $n$ 的字符串 $s$，在问题的第一个变种中，我们希望统计每个前缀 $s[0...i]$ 在同一个字符串的出现次数，在问题的第二个变种中，我们希望统计每个前缀 $s[0...i]$ 在另一个给定字符串 $t$ 中的出现次数。 | + | 在该节我们将同时讨论两个问题。给定一个长度为 $n$ 的字符串 $s$，在问题的第一个变种中，我们希望统计每个前缀 $s[0\ldots i]$ 在同一个字符串的出现次数，在问题的第二个变种中，我们希望统计每个前缀 $s[0\ldots i]$ 在另一个给定字符串 $t$ 中的出现次数。 |
| 首先让我们来解决第一个问题。考虑位置 $i$ 的前缀函数值 $\pi[i]$。根据定义，其意味着字符串 $s$ 一个长度为 $\pi[i]$ 的前缀在位置 $i$ 出现并以 $i$ 为右端点，同时不存在一个更长的前缀满足前述定义。与此同时，更短的前缀可能以该位置为右端点。容易看出，我们遇到了在计算前缀函数时已经回答过的问题：给定一个长度为 $j$ 的前缀，同时其也是一个右端点位于 $i$ 的后缀，下一个更小的前缀长度 $k<j$ 是多少？该长度的前缀需同时也是一个右端点为 $i$ 的后缀。因此以位置 $i$ 为右端点，有长度为 $\pi[i]$ 的前缀，有长度为 $\pi[\pi[i]-1]$ 的前缀，有长度为 $\pi[\pi[\pi[i]-1]-1]$ 的前缀，等等，直到长度变为 $0$。故而我们可以通过下述方式计算答案。 | 首先让我们来解决第一个问题。考虑位置 $i$ 的前缀函数值 $\pi[i]$。根据定义，其意味着字符串 $s$ 一个长度为 $\pi[i]$ 的前缀在位置 $i$ 出现并以 $i$ 为右端点，同时不存在一个更长的前缀满足前述定义。与此同时，更短的前缀可能以该位置为右端点。容易看出，我们遇到了在计算前缀函数时已经回答过的问题：给定一个长度为 $j$ 的前缀，同时其也是一个右端点位于 $i$ 的后缀，下一个更小的前缀长度 $k<j$ 是多少？该长度的前缀需同时也是一个右端点为 $i$ 的后缀。因此以位置 $i$ 为右端点，有长度为 $\pi[i]$ 的前缀，有长度为 $\pi[\pi[i]-1]$ 的前缀，有长度为 $\pi[\pi[\pi[i]-1]-1]$ 的前缀，等等，直到长度变为 $0$。故而我们可以通过下述方式计算答案。 | ||
2020-2021/teams/legal_string/前缀函数与_kmp_算法_lgwza.1594909446.txt.gz · 最后更改: 2020/07/16 22:24 由 lgwza
