字符串无穷幂比较的简单应用

· · 算法·理论

1. 前置约定

2. 周期引理

2.1 周期定义

对于字符串 S 和正整数 p，若 \forall 0 \le i<|S|-p, S[i]=S[i+p]，则称 p 为字符串 S 的一个周期。

根据周期的定义，A^n 具有周期 |A|。

2.2 引理内容

Fine-Wilf 定理：

对于字符串 S，其同时拥有两个不同周期 p,q。
若 |S| \ge p+q-\gcd(p,q)，则 \gcd(p,q) 也是 S 的周期。

先来感性理解一下，考虑 p=5,q=8，公式给出的下界 |S|_{\min}=5+8-1=12。

该定理说明，当 |S| \ge 12 时，S 的所有字符必然相等，否则存在反例。

本文中使用 Fine-Wilf 定理的弱化版本：

引理 1：

对于字符串 S，其同时拥有两个不同周期 p,q。
若 |S| \ge p+q，则 \gcd(p,q) 也是 S 的周期。

这一结论称作弱周期定理。

:::::success[引理 1 的证明]

不妨设 p>q，下证 p-q 是 S 的周期。

即证 \forall 0 \le i <|S|-p-q,S[i]=S[i+p-q]。

下证 \gcd(p,q) 是 S 的周期。

因为 p-q 是 S 的周期，可以不断重复如下过程直到 p=q：

当 p=q 时，由 GCD 的更相减损术得，最终的数一定为 \gcd(p,q)。

:::::

3. 无穷次幂比较

引理 2：

比较 A^{\infty} 与 B^{\infty}，等价于比较 AB 与 BA。

还是先直观感受一下。我们声称，A^{\infty} 与 B^{\infty} 发生“首次不同”的位置，与 AB 和 BA 发生“首次不同”的位置必然相同。

考虑 A=\tt{ab}, B=\tt{a}，对于 A^{\infty} 与 B^{\infty} ：

对于 AB 与 BA：

对于引理 2，给出一个感性理解：

对于字典序比较，平凡的方法是用一个指针顺序扫描 A^{\infty} 与 B^{\infty}，直到出现“首次不同”。现在想象用这种方法比较 AB 与 BA 的过程。

:::::success[引理 2 的证明]

若 AB=BA，容易证明 \exists C, A=C^n, B=C^m。显然 A^{\infty}=B^{\infty}，命题自然成立。

下面假定 AB \ne BA。

设 \operatorname{LCP}(A^{\infty},B^{\infty})=k。根据定义，其满足以下两个性质：

不妨设 A^{\infty}<B^{\infty}，必然有 A^{\infty}[k] < B^{\infty}[k]。

下证 k<|A|+|B|。

假设 k \ge |A|+|B|，此时 A^{\infty} 和 B^{\infty} 的前 |A|+|B| 个字符必定相同，取出这 |A|+|B| 个字符记为字符串 C。

因为 C 是 A^{\infty} 的前缀，所以 C 具有周期 |A|，同理其具有周期 |B|。

而 |C| = |A|+|B| ，根据引理 1 得 x=\gcd(|A|,|B|) 必然是 |C| 的周期。

这说明 A,B 都是由长为 x 的子串组成，即 \exists D, A=D^u, B=D^v，其中 u,v \in \mathbb{N}^+ 且 |D|=x。

此时 AB=D^x D^y=D^{x+y}，BA=D^y D^x=D^{y+x}，得 AB=BA，与假定矛盾。

下证 AB 的前 k+1 个字符与 A^{\infty} 相同。

即 \forall 0 \le i \le k, (AB)[i]=A^{\infty}[i]。

同理可得 BA 的前 k+1 个字符与 B^{\infty} 相同。

至此，得到结论：

AB<BA \iff (AB)[k]<(BA)[k] \iff A^{\infty}[k]<B^{\infty}[k] \iff A^{\infty}<B^{\infty}

:::::

引理 3：

若 A^{\infty} \ne B^{\infty}，则 \operatorname{LCP}(A^{\infty},B^{\infty})=\operatorname{LCP}(AB,BA)。

可以直接由引理 2 的证明过程得到。

引理 4：

比较 A 与 B^{\infty}，等价于比较 A 与 BA。

:::::success[引理 4 的证明] 显然 A \ne B^{\infty}，只需证 A<B^{\infty} \iff A<BA。

4. 应用

4.1 直接应用

如果要比较 A^{\infty} 与 B^{\infty} 的字典序，直观的想法是将 A,B 循环 \operatorname{lcm}(|A|,|B|) 次后再比较。视 |A|,|B| 与 n 同阶，最坏复杂度 O(n^2)。

根据引理 2，我们可以直接比较 AB 与 BA，复杂度 O(n)。

类似地，在某些模拟题中，我们可能需要比较两个循环小数的大小。对于循环节，可以使用这种方法比较。

4.2 拼数

题面见 P1012 [NOIP 1998 提高组] 拼数。

定义字符串集合上的二元关系 \prec，定义 A \prec B 当且仅当 AB>BA。易证 \prec 具有反自反性、非对称性、连接性。

下证 \prec 具有传递性：

设字符串 A,B,C 满足 AB<BA 且 BC<CB。

根据引理 2，A^{\infty}<B^{\infty} 且 B^{\infty}<C^{\infty}，得 A^{\infty}<C^{\infty}。根据引理 2 得 AC<CA。

因此，\prec 是字符串集合上的严格全序。根据邻项交换的理论，将给出的字符串数组 S_i 排序使得 \forall 1 \le i < n, S_i \prec S_{i+1} 即可。

4.3 树的最小表示

给出一棵有根树，点有点权，求字典序最小的 DFS 序列。

考虑对于点 u 先递归求出其儿子 v 的最小表示，然后将它们排序得到 u 的最小表示。

这里我们需要按照 4.2 中定义的 \prec 进行排序。

使用链表来存储序列，瓶颈仅在于排序。直观感受是复杂度为 O(n^2)。事实上根据启发式合并的理论，复杂度可以分析到 O(n \log n)。

:::::success[O(n \log n) 的证明] 对于树上节点 u，比较两个儿子 v_i, v_j 的最小表示的代价为 O\left(\min(|v_i|,|v_j|)\right)。

假定采用随机快速排序，最终排序完成后排名为 i 和 j 的两个元素发生比较的概率为 \frac{2}{|i-j|+1}。

因此，节点 u 处快速排序的期望比较时间代价为：

O\left(\sum\limits_{1 \le i<j<k} \dfrac{1}{|i-j|+1} \min(|v_i|,|v_j|) \right)

将代价拆到 |v_i| 较小的点上。即若 |v_i|\le |v_j|，将比较代价 |v_i| 视为 v_i 的代价。

对于一个固定的 v_i，设 A_i 为满足 |v_j| \ge |v_i| 的所有 j 的集合。由于 u 的总大小为 |u|，则：

|A_i| |v_i| \le \sum\limits_{j \in A_i} |v_j| \le |u| \implies |A_i| \le \dfrac{|u|}{|v_i|} $\sum\limits_{j \in A_i} \frac{1}{|i-j|+1} \le 2\sum\limits_{k=1}^{|A_i|} \frac{1}{k}=O(\log |A_i|) \le O\left(\log \frac{|u|}{|v_i|}\right)

所以 u 处排序的期望代价为 O\left(\sum |v_i| \log \frac{|u|}{|v_i|} \right)，将全树代价求和为总代价。

考虑树中的节点 x，其在每一个祖先 u 处都作为子树 v_i 的一部分参与计算，贡献为 \log \frac{|u|}{|v_i|}。

设 x 到根节点的路径为 u_0,u_1,u_2,\cdots,u_d，其中 |u_0|=n, u_d=x。则其总贡献

\sum_{i=0}^{d-1} \log \frac{|u_i|}{|u_{i+1}|}=\log\left(\prod_{i=1}^{d-1} \frac{|u_i|}{|u_{i+1}|} \right)=\log \frac{|u_0|}{|u_d|}=\log \frac{n}{|x|} \le \log n

由于每个节点的贡献都不超过 O(\log n)，均摊复杂度为 O(n \log n)。 :::::

:::::info[O(n \log n) 的实现]

const int N = 1e6 + 5;
int n, a[N];
vector<int> e[N];
struct node {
    int val;
    node* nxt;
    node(int v) : val(v), nxt(nullptr) {}
};
node *h[N], *t[N];
void dfs(int u, int fa) {
    vector<int> vec;
    for (int v : e[u]) {
        if (v != fa) dfs(v, u), vec.emplace_back(v);
    }
    sort(vec.begin(), vec.end(), [&](int x, int y) -> bool {
        node *a = h[x], *b = h[y];
        bool fx = 0, fy = 0;
        while (a && b) {
            if (a->val != b->val) return a->val < b->val;
            a = a->nxt, b = b->nxt;
            if (!a && !fx) a = h[y], fx = 1;
            if (!b && !fy) b = h[x], fy = 1; 
        } 
        return false;
    });
    h[u] = t[u] = new node(a[u]);
    for (int v : vec) t[u]->nxt = h[v], t[u] = t[v];
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    dfs(1, -1);
    for (node *i = h[1]; i; i = i->nxt) cout << i->val << ' ';
}

:::::

树的最小表示的一个应用是判断树同构。注意到对于同构的树，其括号序最小表示也是相同的，可以得到一个 O(n \log n) 的确定性算法。

通过压位可以做到 O\left(\dfrac{n\log n}{w}\right)，和树 Hash 具有同样优秀的复杂度。但是这个做法比较繁杂，在此不展开，有兴趣的读者可以阅读参考资料。

4.4 ARC175F

题面见 AT_arc175_f [ARC175F] Append Same Characters。

:::::success[题解]

两个操作的顺序显然没有什么关系，不妨先进行完所有操作一再进行操作二。而操作二就是冒泡排序，其操作次数等于逆序对数。因此本题表述为：

给出 n 个字符串 S_i，你可以任选一个字符串 X，令 S_i \gets S_iX。最小化序列逆序对数与 |X| 的和。

下面分析复杂度时，视 n, \sum |S_i| 同阶。

直接对着逆序对数分析很难，考虑 X 对每一对 (i,j) 的影响。设一对字符串是 A,B，不妨设 i<j,A<B,|A|<|B|。我们讨论满足什么条件可以使得 AX>BX。

下面先对 i<j 时 X>CX 这一种情况考虑。另一种情况是对称的 X<CX。

根据引理 4，我们有 X>CX \iff X>C^{\infty}。这说明 C^{\infty} 是一个阈值，我们并不需要关心 X 的内容，只需要关注 X 的字典序越过了哪些 C^{\infty}。

现在我们需要找出所有的 C^{\infty}，可以使用多项式哈希解决。用一个 vector 记录哈希值为 x 的字符串下标集合 H(x)。

依次枚举 S_i 并将 S_i 作为 B，设当前枚举到了前缀长度 k，可以求出前缀哈希 h_k。在 H(h_k) 中，二分找到满足 i<j 的所有 A，求出 C 后计入 C^{\infty} 的出现次数。

讨论 C^{\infty} 的贡献：

这个做法也说明本质不同的 C^{\infty} 只有 O(n) 种，每个本质不同的 C^{\infty} 的贡献为上述两种情况的出现次数作差。

因此，上述两种情形可以统一成一种。在 O(n \log n) 内求出原本的逆序对数后，我们只需对变化量考虑。

将所有 C^{\infty} 排序并去重后，X 有贡献的区间是一段前缀。这里的排序使用了引理 2，即 4.2 中的 \prec。

对所有 C^{\infty} 扫描线。依次增大 X 的字典序，每当 X 越过一个 C^{\infty} 时，将对应的变化量加入答案。此时我们知道了 X \in (Y_k^{\infty},Y_{k+1}^{\infty}] 时，S_i 的逆序对数。贪心地，我们希望 |X| 最小。

现在整个问题只差最后一步：求满足 X \in (Y_k^{\infty},Y_{k+1}^{\infty}] 的 |X|_{\min}。

记 l=\operatorname{LCP}(Y_k^{\infty},Y_{k+1}^{\infty})。根据引理 3，l=\operatorname{LCP}(Y_k Y_{k+1}, Y_{k+1}Y_k)，可以使用二分哈希 O(\log n) 算出。

在扫描线的最后，当 X 越过所有 Y^{\infty}_k 时产生一个 corner case。对于这种情况，我们先找到 Y^{\infty}_{\max}。

代码用到的唯一字符串算法是哈希，复杂度 O(n \log^2 n)。

理清所有思路后码量虽然大，但并不难写。 :::::

:::::info[代码]

const int N = 3e5 + 5;
const u64 base = 13331;

int n, id[N];
u64 b[N];
string s[N];
vector<u64> h[N];
umap<u64, vector<int>> mp;

u64 sub(int i, int l, int r) {return h[i][r] - h[i][l - 1] * b[r - l + 1];}

i64 merge(int l, int r) {     // 求原逆序对数
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    i64 res = merge(l, mid) + merge(mid + 1, r);
    vector<int> vec;
    auto cmp = [&](int x, int y) -> bool {
        int n = s[x].size() - 1, m = s[y].size() - 1;
        int l = 1, r = min(n, m), lcp = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (h[x][mid] == h[y][mid]) l = mid + 1, lcp = mid;
            else r = mid - 1;
        }
        if (lcp == min(n, m)) return n <= m;
        return s[x][lcp + 1] <= s[y][lcp + 1];
    };
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (cmp(id[i], id[j])) vec.emplace_back(id[i++]);
        else vec.emplace_back(id[j++]), res += mid - i + 1;
    }
    while (i <= mid) vec.emplace_back(id[i++]);
    while (j <= r) vec.emplace_back(id[j++]);
    copy(vec.begin(), vec.end(), id + l);
    return res;
}

struct node {
    int id, st, len; i64 val;
    node(int a = 0, int b = 0, int c = 0, i64 d = 0) : id(a), st(b), len(c), val(d) {}
};
int lcp(const node& u, const node& v) {
    int n = u.len, m = v.len, l = 1, r = n + m, lcp = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        u64 x = mid <= n ? sub(u.id, u.st, u.st + mid - 1) : sub(u.id, u.st, u.st + n - 1) * b[mid - n] + sub(v.id, v.st, v.st + mid - n - 1);
        u64 y = mid <= m ? sub(v.id, v.st, v.st + mid - 1) : sub(v.id, v.st, v.st + m - 1) * b[mid - m] + sub(u.id, u.st, u.st + mid - m - 1);
        if (x == y) l = mid + 1, lcp = mid;
        else r = mid - 1;
    } return lcp;
}

void _main() {
    b[0] = 1;
    for (int i = 1; i < N; i++) b[i] = b[i - 1] * base;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i], s[i] = ' ' + s[i];
        int m = s[i].size() - 1;
        h[i].resize(m + 5, 0);
        for (int j = 1; j <= m; j++) h[i][j] = h[i][j - 1] * b[1] + s[i][j];
        mp[h[i][m]].emplace_back(i);
    }
    iota(id + 1, id + n + 1, 1);
    i64 inv = merge(1, n);

    // 处理出所有 C^inf 排序后去重
    vector<node> inf, vec;
    for (int i = 1; i <= n; i++) {
        int m = s[i].size() - 1;
        for (int k = 1; k < m; k++) {
            if (mp.find(h[i][k]) == mp.end()) continue;
            auto& v = mp[h[i][k]];
            int a = lower_bound(v.begin(), v.end(), i) - v.begin();
            int b = upper_bound(v.begin(), v.end(), i) - v.begin();
            inf.emplace_back(i, k + 1, m - k, a - (v.size() - b));
        }
    }
    stable_sort(inf.begin(), inf.end(), [&](const node& u, const node& v) -> bool {
        int n = u.len, m = v.len, p = lcp(u, v);
        if (p == n + m) return false;
        char x = p < n ? s[u.id][u.st + p] : s[v.id][v.st + p - n];
        char y = p < m ? s[v.id][v.st + p] : s[u.id][u.st + p - m];
        return x < y;
    });
    for (auto& u : inf) {
        if (vec.empty()) vec.emplace_back(u);
        else if (lcp(vec.back(), u) == vec.back().len + u.len) vec.back().val += u.val;
        else vec.emplace_back(u);
    }

    // 扫描线
    int len = vec.size();
    i64 res = 0, cur = 0;
    for (int k = 0; k < len - 1; k++) {
        cur += vec[k].val;
        res = min(res, cur + lcp(vec[k], vec[k + 1]) + 1);
    }
    auto corner = [&]() -> void {
        if (vec.empty()) return;
        auto [id, st, len, val] = vec.back(); cur += val;
        int pre = 0;
        while (pre < len && s[id][st + pre] == 'z') pre++;
        if (pre >= len) return;
        res = min(res, cur + pre + 1);
    };
    corner(), cout << inv + res;
}

:::::

参考资料