2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza [2020/07/16 22:22] lgwza |
2020-2021:teams:legal_string:前缀函数与_kmp_算法_lgwza [2020/07/16 22:24] (当前版本) lgwza [统计每个前缀的出现次数] |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| 给定一个长度为 $n$ 的字符串 $s$，其**前缀函数**被定义为一个长度为 $n$ 的数组 $\pi$。其中 $\pi[i]$ 的定义是： | 给定一个长度为 $n$ 的字符串 $s$，其**前缀函数**被定义为一个长度为 $n$ 的数组 $\pi$。其中 $\pi[i]$ 的定义是： | ||
| - | - 如果子串 $s[0\ldots i]$ 有一对相等的真前缀与真后缀：$s[0...k-1]$ 和 $s[i-(k-1)...i]$，那么 $\pi[i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等）的长度，也就是 $\pi[i]=k$； | + | - 如果子串 $s[0\ldots i]$ 有一对相等的真前缀与真后缀：$s[0\ldots k-1]$ 和 $s[i-(k-1)\ldots i]$，那么 $\pi[i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等）的长度，也就是 $\pi[i]=k$； |
| - 如果不止有一对相等的，那么 $\pi[i]$ 就是其中最长的那一对的长度； | - 如果不止有一对相等的，那么 $\pi[i]$ 就是其中最长的那一对的长度； | ||
| - 如果没有相等的，那么 $\pi[i]=0$。 | - 如果没有相等的，那么 $\pi[i]=0$。 | ||
| - | 简单来说 $\pi[i]$ 就是，子串 $s[0...i]$ 最长的相等的真前缀与真后缀的长度。 | + | 简单来说 $\pi[i]$ 就是，子串 $s[0\ldots i]$ 最长的相等的真前缀与真后缀的长度。 |
| 用数学语言描述如下： $$ | 用数学语言描述如下： $$ | ||
| - | \pi[i]=\max_{k=0...i}\{k:s[0...k-1]=s[i-(k-1)...i]\} | + | \pi[i]=\max_{k=0\ldots i}\{k:s[0\ldots k-1]=s[i-(k-1)\ldots i]\} |
| $$ 特别地，规定 $\pi[0]=0$。 | $$ 特别地，规定 $\pi[0]=0$。 | ||
| 行 104: | 行 104: | ||
| 在第一个优化中，我们讨论了计算 $\pi[i+1]$ 时的最好情况：$s[i+1]=s[\pi[i]]$，此时 $\pi[i+1]=\pi[i]+1$。现在让我们沿着这个思路走得更远一点：讨论当 $s[i+1]\ne s[\pi[i]]$ 时如何跳转。 | 在第一个优化中，我们讨论了计算 $\pi[i+1]$ 时的最好情况：$s[i+1]=s[\pi[i]]$，此时 $\pi[i+1]=\pi[i]+1$。现在让我们沿着这个思路走得更远一点：讨论当 $s[i+1]\ne s[\pi[i]]$ 时如何跳转。 | ||
| - | 失配时，我们希望找到对于子串 $s[0...i]$，仅次于 $\pi[i]$ 的第二长度 $j$，使得在位置 $i$ 的前缀性质仍得以保持，也即 $s[0...j-1]=s[i-j+1...i]$： $$ | + | 失配时，我们希望找到对于子串 $s[0\ldots i]$，仅次于 $\pi[i]$ 的第二长度 $j$，使得在位置 $i$ 的前缀性质仍得以保持，也即 $s[0\ldots j-1]=s[i-j+1\ldots i]$： $$ |
| \overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1} | \overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1} | ||
| - | $$ 如果我们找到了这样的长度 $j$，那么仅需要再次比较 $s[i+1]$ 和 $s[j]$。如果它们相等，那么就有 $\pi[i+1]=j+1$。否则，我们需要找到子串 $s[0...i]$ 仅次于 $j$ 的第二长度 $j^{(2)}$，使得前缀性质得以保持，如此反复，直到 $j=0$。如果 $s[i+1]\ne s[0]$，则 $\pi[i+1]=0$。 | + | $$ 如果我们找到了这样的长度 $j$，那么仅需要再次比较 $s[i+1]$ 和 $s[j]$。如果它们相等，那么就有 $\pi[i+1]=j+1$。否则，我们需要找到子串 $s[0\ldots i]$ 仅次于 $j$ 的第二长度 $j^{(2)}$，使得前缀性质得以保持，如此反复，直到 $j=0$。如果 $s[i+1]\ne s[0]$，则 $\pi[i+1]=0$。 |
| - | 观察上图可以发现，因为 $s[0...\pi[i]]=s[i-\pi[i]+1...i]$，所以对于 $s[0...i]$ 的第二长度 $j$，有这样的性质： $$ | + | 观察上图可以发现，因为 $s[0\ldots \pi[i]]=s[i-\pi[i]+1\ldots i]$，所以对于 $s[0\ldots i]$ 的第二长度 $j$，有这样的性质： $$ |
| - | s[0...j-1]=s[i-j+1...i]=s[\pi[i]-j...\pi[i]-1] | + | s[0\ldots j-1]=s[i-j+1\ldots i]=s[\pi[i]-j\ldots \pi[i]-1] |
| $$ 也就是说 $j$ 等价于子串 $s[\pi[i]-1]$ 的前缀函数值，即 $j=\pi[\pi[i]-1]$。同理，次于 $j$ 的第二长度等价于 $s[j-1]$ 的前缀函数值，$j^{(2)}=\pi[j-1]$ | $$ 也就是说 $j$ 等价于子串 $s[\pi[i]-1]$ 的前缀函数值，即 $j=\pi[\pi[i]-1]$。同理，次于 $j$ 的第二长度等价于 $s[j-1]$ 的前缀函数值，$j^{(2)}=\pi[j-1]$ | ||
| 行 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.1594909335.txt.gz · 最后更改: 2020/07/16 22:22 由 lgwza
