Solution. LG3426 [POI2005]SZA-Template

Description 展开目录

用一个印章印出字符串 $S$，印章每次会将所有字符印到纸上，印上去的字母无法被覆盖，求最小的印章长度。

$|S|\le 5\times {10}^5$

Solution 展开目录

若印章能印出 $S$，则必然能印出 $S$ 的最长 border，即 $nx{t}_i$，这启发我们 dp。

设 $f_i$ 表示能引出 $S_{0\dots i}$ 的最小印章长度，则 $f_i=i\mathrm{or}{f}_{nx{t}_i}$。

考虑什么时候能够通过 $nx{t}_i$ 转移，这一点题解里普遍很简略。

已知，$S_{0\dots i}$ 的 border 部分能够通过印章印出，我们希望知道当前印章能否印出中间的部分，于是我们查找是否存在 $f_j$ 使得 $f_j=f_{nx{t}_i},j\ge i-nx{t}_i$，前者保证了 $f_j$ 与 $f_{nx{t}_i}$ 对应了同一个印章，后者保证了 $f_j$ 覆盖了我们未知的部分。

具体实现时我们维护每个 dp 值对应的最大下标即可。

Code 展开目录

namespace Main{
    const int N = 500005;
    int n, nxt[N], f[N], cnt[N];
    char s[N];
    void Main(){
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for(int i = 2, j = 0; i <= n; i++){
            while(j && s[i] != s[j+1]) j = nxt[j];
            if(s[i] == s[j+1]) j++;
            nxt[i] = j;
        }
        for(int i = 1; i <= n; i++){
            f[i] = i;
            if(cnt[f[nxt[i]]] >= i - nxt[i]) f[i] = f[nxt[i]];
            cnt[f[i]] = i;
        }
        write(f[n]);
        return;
    }
}

本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。