Solution. LG3426 [POI2005]SZA-Template

Description

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

$|S|\le5\times10^5$

Solution

若印章能印出 $S$，则必然能印出 $S$ 的最长 border，即 $nxt_i$，这启发我们 dp。

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

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

已知，$S_{0\dots i}$ 的 border 部分能够通过印章印出，我们希望知道当前印章能否印出中间的部分，于是我们查找是否存在 $f_j$ 使得 $f_j=f_{nxt_i},j\ge i-nxt_i$，前者保证了 $f_j$ 与 $f_{nxt_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 国际许可协议 进行许可。