Q：我们随机问 \(k\) 个数，取这些数的最大值 \(m\)，\(m\) 应该不会距离 \(\frac{k(k+1)}{n}\) 太远 的结论为什么成立？
A：这个结论来自于统计学中的极值理论。具体来说，当我们从一个已知范围内随机选择一些数，并取这些数中的最大值时，这个最大值有一定的统计规律。
假设我们从一个包含 ( \(n\) ) 个数的序列中随机选择 ( \(k\) ) 个数。为了简单起见，我们假设这些数是 ( \(1, 2, 3, \ldots, n\) )。
-
最大值的期望：
当我们从 ( \(n\) ) 个数中随机选择 ( \(k\) ) 个数时，这 ( \(k\) ) 个数的最大值 ( \(m\) ) 的期望值可以近似为 ( \(\frac{k}{n} \times n\) )，即 ( \(\frac{k}{n}\) ) 是选择的比例，然后乘以 ( \(n\) ) 就得到了期望值。 -
统计分布：
具体来说，假设 ( \(X_1, X_2, \ldots, X_k\) ) 是从集合 ( \(\{1, 2, \ldots, n\}\) ) 中随机选择的 ( \(k\) ) 个数，这些数是独立同分布的随机变量。定义 ( M ) 为这 ( k ) 个数中的最大值，即 ( \(M = \max(X_1, X_2, \ldots, X_k)\) )。我们感兴趣的是 ( \(M\) ) 的分布及其期望值。可以证明，当 ( \(n\) ) 非常大时，( \(M\) ) 的分布会逼近一个特定的形式，使得 ( \(M\) ) 的期望值约为 ( \(\frac{k(n+1)}{k+1}\) ) 的某种常数倍。
然而，为了更简单的近似，我们可以使用 ( \(\frac{k(k+1)}{n}\) ) 作为一个近似值。
-
近似的推导：
- 从 ( \(n\) ) 个数中选 ( \(k\) ) 个数，期望最大值约为 ( \(n \times [1 - (1 - \frac{1}{n})^k]\) )。
- 由于 ( \((1 - \frac{1}{n})^k \approx e^{-k/n}\) )，当 ( \(k\) ) 远小于 ( \(n\) ) 时。
- 所以期望最大值可以近似为 ( \(n \times (1 - e^{-k/n})\) )。
当 ( \(k\) ) 和 ( \(n\) ) 较大时，这个表达式可以进一步简化为 ( \(\frac{k(k+1)}{n}\) ) 作为一种经验性的估计。
-
实际应用：
这个结论的实际应用在于理解随机抽样中的最大值行为，尤其是当样本大小 ( \(k\) ) 相对于总体大小 ( \(n\) ) 较大时。这种理解可以帮助在设计算法和进行概率估计时得到更合理的预期。
因此，“我们随机问 ( \(k\) ) 个数，取这些数的最大值 ( \(m\) )，( \(m\) ) 应该不会距离 ( \(\frac{k(k+1)}{n}\) ) 太远” 是基于上述极值理论的一个经验性结论。
Q：基于基数排序的后缀数组 C++ 实现，不要使用向量和引用，直接在全局声明
A：
#include <iostream>
#include <cstring>
const int MAXN = 100000; // 最大字符串长度
const int ALPHABET_SIZE = 256; // 字符集大小（ASCII）
// 全局变量
int suffixArray[MAXN];
int rank[MAXN];
int temp[MAXN];
int count[MAXN];
void radixSort(int n, int k) {
memset(count, 0, sizeof(count));
// 计算每个排名出现的次数
for (int i = 0; i < n; ++i) {
count[rank[suffixArray[i]]]++;
}
// 累加计数
for (int i = 1; i <= k; ++i) {
count[i] += count[i - 1];
}
// 基数排序
for (int i = n - 1; i >= 0; --i) {
temp[--count[rank[suffixArray[i]]]] = suffixArray[i];
}
// 复制回原数组
for (int i = 0; i < n; ++i) {
suffixArray[i] = temp[i];
}
}
void buildSuffixArray(const char* s) {
int n = strlen(s);
int m = ALPHABET_SIZE;
// 初始化排名和后缀数组
for (int i = 0; i < n; ++i) {
suffixArray[i] = i;
rank[i] = s[i];
}
// 初始基数排序
radixSort(n, m);
// 倍增排序
for (int k = 1; k < n; k <<= 1) {
auto cmp = [k](int i, int j) {
if (rank[i] != rank[j]) return rank[i] < rank[j];
int ri = (i + k < n) ? rank[i + k] : -1;
int rj = (j + k < n) ? rank[j + k] : -1;
return ri < rj;
};
// 使用自定义比较器进行排序
for (int i = 0; i < n; ++i) {
temp[i] = suffixArray[i];
}
std::sort(temp, temp + n, cmp);
// 更新排名
rank[temp[0]] = 0;
for (int i = 1; i < n; ++i) {
rank[temp[i]] = rank[temp[i - 1]] + (cmp(temp[i - 1], temp[i]) ? 1 : 0);
}
for (int i = 0; i < n; ++i) {
suffixArray[i] = temp[i];
}
}
}
int main() {
char s[MAXN];
std::cin >> s;
buildSuffixArray(s);
for (int i = 0; i < strlen(s); ++i) {
std::cout << suffixArray[i] << " ";
}
std::cout << std::endl;
return 0;
}
代码说明
-
全局变量：
suffixArray: 存储后缀的起始位置。rank: 存储每个后缀的排名。temp: 用于排序过程中的临时存储。count: 计数排序用的计数数组。
-
radixSort函数：- 使用基数排序对后缀数组进行排序。先计算每个排名出现的次数，然后进行排序，并将结果复制回原数组。
-
buildSuffixArray函数：- 初始化排名和后缀数组，并调用
radixSort进行初始排序。 - 使用倍增策略进行排序，每次将前缀长度翻倍。
- 自定义比较器用于更新排名，并在每次迭代中进行排序。
- 初始化排名和后缀数组，并调用
-
main函数：- 读取输入字符串，调用
buildSuffixArray函数构造后缀数组，并输出结果。
- 读取输入字符串，调用
Q：如何C++求height数组呢？
A：
height 数组的计算步骤
-
初始化：计算每个后缀的排名，用于查找
height数组的值。 -
遍历所有后缀：
- 通过当前后缀与前一个后缀的公共前缀长度来计算
height数组。 - 使用一个辅助变量
h来存储当前计算的最长公共前缀长度，初始值为 0。
- 通过当前后缀与前一个后缀的公共前缀长度来计算
-
更新 LCP 值：
- 对于每个后缀，根据当前后缀和前一个后缀的公共前缀长度来更新
height数组。 - 确保在计算过程中更新
h值以避免重复计算。
- 对于每个后缀，根据当前后缀和前一个后缀的公共前缀长度来更新
C++ 实现
#include <iostream>
#include <cstring>
const int MAXN = 100000; // 最大字符串长度
// 全局变量
int suffixArray[MAXN];
int rank[MAXN];
int height[MAXN];
// 计算height数组（LCP数组）
void buildHeightArray(const char* s) {
int n = strlen(s);
int h = 0;
// Initialize rank array
for (int i = 0; i < n; ++i) {
rank[suffixArray[i]] = i;
}
for (int i = 0; i < n; ++i) {
if (rank[i] > 0) {
int j = suffixArray[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
++h;
}
height[rank[i]] = h;
if (h > 0) {
--h; // Adjust h for the next suffix
}
} else {
height[rank[i]] = 0;
}
}
}
int main() {
char s[MAXN];
std::cin >> s;
// 假设suffixArray已经被计算
// 例如可以调用之前的buildSuffixArray函数
// buildSuffixArray(s);
buildHeightArray(s);
for (int i = 1; i < strlen(s); ++i) { // height[0] 通常被忽略
std::cout << height[i] << " ";
}
std::cout << std::endl;
return 0;
}
代码说明
-
全局变量：
suffixArray: 存储后缀的起始位置。rank: 存储每个后缀的排名。height: 存储LCP值的数组。
-
buildHeightArray函数：- 初始化
rank数组，记录每个后缀的排名。 - 遍历每个后缀，计算其与前一个后缀的公共前缀长度，并更新
height数组。 - 使用一个变量
h来跟踪当前的公共前缀长度，并在计算过程中更新。
- 初始化
-
main函数：- 读取输入字符串。
- 调用
buildHeightArray函数计算height数组，并输出结果。
Q：后缀自动机的原理
A：
后缀自动机的原理
-
定义：
- 后缀自动机是一个最小的、包含所有字符串后缀的有向图。它是一个最小的确定性有限自动机（DFA），可以接受给定字符串的所有后缀。
-
构建：
- 后缀自动机可以通过扩展的方式逐步构建。我们从空字符串开始，逐步添加每个字符，并维护一个状态图，确保它能够接受当前已处理的所有后缀。
- 每个状态表示某个后缀的前缀。状态之间的转移表示字符的添加。新的状态和转移是通过将当前状态与新字符的组合进行扩展得到的。
-
状态和转移：
- 状态：表示字符串的一个子串的所有后缀。
- 转移：从一个状态到另一个状态的边表示字符的添加。每个状态的转移边是唯一的。
-
建造过程：
- 起始状态：从空串开始。
- 添加字符：对于每个字符，将它添加到自动机中。对于新字符，创建一个新的状态，并将所有必要的转移添加到状态图中。
- 状态合并：在构建过程中，有时需要合并状态，以保持自动机的最小化。合并状态可以通过最小化合并相同的后缀来完成。
-
时间复杂度：
- 后缀自动机的构建时间复杂度为
O(n)，其中n是字符串的长度。由于每个字符仅会处理常数次，因此构建过程是线性的。
- 后缀自动机的构建时间复杂度为
-
应用：
- 模式匹配：可以用来快速查找子串。
- 字符串分析：可以用来计算字符串的所有子串和子串出现的次数。
- 计算 LCP 数组：可以利用后缀自动机计算字符串的最长公共前缀数组（LCP）。
示例
假设我们要构建字符串 s = "abac" 的后缀自动机：
-
初始化：
- 创建一个空的起始状态。
-
添加字符：
- 添加字符
a，创建新状态S1，并添加边S0 --a--> S1。 - 添加字符
b，创建新状态S2，并添加边S1 --b--> S2。 - 添加字符
a，创建新状态S3，并添加边S2 --a--> S3。 - 添加字符
c，创建新状态S4，并添加边S3 --c--> S4。
- 添加字符
-
状态合并：
- 在实际构建过程中，根据需要合并状态以保持最小化。
代码示例（C++）
下面是一个简单的 C++ 实现，用于构建后缀自动机：
#include <iostream>
#include <vector>
#include <cstring>
const int MAXN = 1000; // 最大字符串长度
const int ALPHABET_SIZE = 26; // 字符集大小（小写字母）
struct State {
std::vector<int> next; // 转移数组
int link; // 后缀链接
int length; // 到达该状态的字符串长度
State(int alphabetSize) : next(alphabetSize, -1), link(-1), length(0) {}
};
State states[MAXN * 2];
int lastState, size;
void init() {
size = lastState = 0;
states[size++] = State(ALPHABET_SIZE); // 创建起始状态
}
void extend(char c) {
int cur = size++;
states[cur] = State(ALPHABET_SIZE);
states[cur].length = states[lastState].length + 1;
int p = lastState;
while (p != -1 && states[p].next[c - 'a'] == -1) {
states[p].next[c - 'a'] = cur;
p = states[p].link;
}
if (p == -1) {
states[cur].link = 0;
} else {
int q = states[p].next[c - 'a'];
if (states[p].length + 1 == states[q].length) {
states[cur].link = q;
} else {
int clone = size++;
states[clone] = states[q];
states[clone].length = states[p].length + 1;
while (p != -1 && states[p].next[c - 'a'] == q) {
states[p].next[c - 'a'] = clone;
p = states[p].link;
}
states[q].link = states[cur].link = clone;
}
}
lastState = cur;
}
int main() {
char s[MAXN];
std::cin >> s;
init();
for (int i = 0; i < strlen(s); ++i) {
extend(s[i]);
}
// 输出状态信息
for (int i = 0; i < size; ++i) {
std::cout << "State " << i << ": Length = " << states[i].length << ", Link = " << states[i].link << std::endl;
}
return 0;
}
代码说明
-
State结构体：next：表示转移数组，每个字符到达的新状态。link：表示后缀链接。length：表示到达该状态的字符串的长度。
-
init函数：- 初始化状态机，创建起始状态。
-
extend函数：- 将字符添加到自动机中，更新状态和转移。
- 处理新字符时，创建新的状态，并根据需要更新现有状态的转移和后缀链接。
- 通过合并状态保持自动机的最小化。
-
main函数：- 读取输入字符串。
- 调用
extend函数构建后缀自动机。 - 输出每个状态的信息，包括长度和后缀链接。