Z Function

Z-function - Algorithms for Competitive Programming

Analysis

对于一个字符串 \(S\)（下标从 \(1\) 开始），定义 \(z[i]\) 表示 \(S\) 中从 \(i\) 开始的后缀与 \(S\) 的最长公共前缀（LCP）的长度。

直接求 \(z\) 数组是 \(\mathcal{O}(n^2)\) 的，但是如果利用到以往的信息，就可以将暴力优化到 \(\mathcal{O}(n)\) 。

Efficient Algorithm

按照 \(i=1,2,\dots,|s|\)的顺序依次求 \(z\)数组，同时维护当前匹配到最靠右的位置 \(mxpos=\arg \max \{i + z[i] - 1\}\)

记 \((mxpos,mxpos + z[mxpos] - 1)\)为 \((L,R)\)，代表当前与前缀匹配的最靠右的区间。

那么对于一个新扫描的位置 \(i\)，讨论：

1. 若 \(i>R\)，那么曾经的信息都用不上了，暴力从 \(i\) 开始向后尝试匹配。

2. 如果 \(i<R\)，我们尝试利用曾经计算过的信息：

   首先可以肯定 \(S[i,R]=S[i-l+1,r-l+1]\) ,尝试利用所以可以继承 \(z[i-l+1]\)的一部分。

   但如果对应位置超过 \(R\)就不能确定是否可以利用了，所以令 \(z[i]=\min(z[i-l+1],r - i + 1)\)，然后再暴力向后匹配。

int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
    if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
    while (i + z[i] <= n && t[z[i] + 1] == t[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) {l = i; r = i + z[i] - 1;}  
}

Proof of Time Complexity

首先算法正确性显然，空间复杂度显然是 \(\mathcal{O}(n)\) ，就不多做分析了。

证明思路：观察到两种情况下每次有效的暴力比较都会拓展右边界 \(R\) ，而右边界只会变化 \(n\) 次，故线性复杂度。

ARC 058 F - Iroha Loves Strings

给定 \(n\) 个串的序列 \(s_1,s_2,\dots,s_n\) ，选择其中一些串，按照原序列顺序连接起来，使得得到的串长为 \(k\) 且字典序最小。

数据范围：\(1\le n\le 2\times 10^3,1\le |s_i|\le k\le 10^4\)

按顺序拿，先解决可不可以拿，倒序做一个 \(O(nk)\) 的 01 背包预处理 valid[i][j] 表示 \(i\) 及之后的串是否能组合出长度 \(j\) 。

接下来先考虑暴力：设 f[i][j] 表示前 \(i\) 个串，凑出长度为 \(j\) 的最小字典序字符串，转移为字符串比较复杂度，总 \(\mathcal{O}(nk^2)\) 。

考虑优化，对于相同长度，最优解显然只有一个（转移时只从 f[i-1][x] 转移，已经使用）；

对于不同长度两个状态，假设较短的为 \(a\) ，较长的为 \(b\) ，若 \(b\) 长度为 \(|a|\) 的前缀和 \(a\) 不同，则 \(a,b\) 一定有一个没用。

因此当前所有最优解中，短的串必然是长的串的前缀，所有串都可以用最长的最优解 \(S\) 的前缀来表示。

现在考虑 dp 实际在做什么：将以往的某个最优解接上当前串，来替换以往的其他最优解。

即对于以往的两个最优解 \(a,b\) 满足 \(|a|+|s_i|=|b|\) ，如果 \(s_i\) 比 \(S\) 中 \(|a|+1\) 开始的后缀字典序要小，那么长度 \(\ge |a|\) 的以往的最优解都没用了，因此我们可以枚举最靠前的这个位置进行插入（并删除以往多余的后缀）。

可以发现比较的永远是 \(S\) 的一个后缀和 \(s_i\) 的字典序，因此可以用 \(s_i+\#+S\) 跑 Z 函数确定 LCP 后讨论。

这样复杂度就是 \(\mathcal{O}(nk)\) 的了。实在是太细节了绷不住了。

#include<bits/stdc++.h>
using namespace std;

#define N 2007
#define K 10007

char s[N][K], S[K], tmp[K << 1];

bool valid[N][K], pos[K];

int len[N], z[K << 1];

void zfunc(int p) {
    memset(z, 0, sizeof(z));     
    memset(tmp, 0, sizeof(tmp));
    strcpy(tmp + 1, s[p] + 1); 
    tmp[len[p] + 1] = 'z' + 1;
    strcpy(tmp + len[p] + 2, S + 1); 
    tmp[strlen(tmp + 1) + 1] = 'z' + 2;
    int l = 0, r = 0;
    for (int i = 2, lim = strlen(tmp + 1); i <= lim; ++i) {
        if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
        while (i + z[i] <= lim && tmp[z[i] + 1] == tmp[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) {l = i; r = i + z[i] - 1;} 
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
        len[i] = strlen(s[i] + 1);
    }
    for (int i = 1; i <= n + 1; ++i) valid[i][0] = true;
    for (int i = n; i; --i) 
        for (int j = k; j; --j) {
            valid[i][j] |= valid[i + 1][j];
            if (j >= len[i]) valid[i][j] |= valid[i + 1][j - len[i]];
        }

    for (int i = 1; i <= n; ++i) {
        zfunc(i);
        int len_S = strlen(S + 1);
        pos[len_S + 1] = true;
        for (int j = 1, lim = min(k + 1 - len[i], len_S + 1); j <= lim; ++j) 
            if (valid[i + 1][k - (j + len[i] - 1)] && pos[j]) { // update to S[j,j + len[i] - 1]
                int match = z[j + len[i] + 1];
                if (match == len[i]) pos[j + len[i]] = true;
                else if (j + match - 1 == len_S) {
                    strcpy(S + j, s[i] + 1); 
                    pos[len_S + 1] = pos[j + len[i]] = true;
                } else if (match < len[i] && tmp[match + 1] < tmp[j + len[i] + 1 + match]) {
                    strcpy(S + j, s[i] + 1);
                    for (int p = j + match + 1; p <= k; ++p) pos[p] = false;
                    break;
                } 
            }
    }
    puts(S + 1);
    return 0;
}