题目链接：HDU 6583

有一天，Jerry 发现了一个奇怪的打字机。这个打字机又 $2$ 种模式：第一种模式可以花费 $p$ 的代价在最后插入一个任意字符；第二种模式可以花费 $q$ 的代价复制任意一个子串并插在最后。

现在 Jerry 想要给 Tom 写一封信，这封信可以用一个只包含小写字母的字符串 $S$ 表示。可惜 Jerry 很穷所以他想知道写这封信的最小花费。

本题由多组数据。

数据范围：$1 \le \lvert S \rvert \le 2 \times 10 ^ {5}$，$\sum \lvert S \rvert \le 5 \times 10 ^ {6}$。

Solution

从小到大依次处理每个 $i$，维护满足 $s[j : i] \subseteq s[1 : j - 1]$ 的最小的 $j$（其中 $s[i : j]$ 表示 $s$ 从 $i$ 到 $r$ 的子串。那么有 $f(i) = \min \{ f(i - 1) + p, f(j - 1) + q \}$。

代码实现过程中，我们用 $\text{SAM}$ 维护 $s[1 : j - 1]$，如果 $s[1 : j - 1]$ 中包含 $s[j : i + 1]$（当前状态有 $s_i$ 的转移）则不需要进行任何操作。否则加入字符 $s_j$ 并维护 $s[j : i + 1]$ 在自动机上的新的匹配位置，直到满足 $j$ 的定义。

时间复杂度：$\mathcal O(\sum \lvert S \rvert)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 2e5 + 5;

int n, p, q;
long long f[N];
char s[N];

template <int MAX, int S>
struct SAM {
    static const int N = MAX << 1;

    int tot, lst, len[N], lnk[N], nxt[N][S];

    void clear(int x) {
        len[x] = lnk[x] = 0;
        std::fill(nxt[x], nxt[x] + S, 0);
    }
    void clear() {
        clear(tot = lst = 1);
    }
    void extend(int x) {
        int cur = ++tot, p = lst;
        clear(cur);
        len[cur] = len[lst] + 1;
        for (; p >= 1 && nxt[p][x] == 0; nxt[p][x] = cur, p = lnk[p]);
        if (p == 0) {
            lnk[cur] = 1;
        } else {
            int q = nxt[p][x];
            if (len[q] == len[p] + 1) {
                lnk[cur] = q;
            } else {
                int c = ++tot;
                clear(c);
                len[c] = len[p] + 1;
                lnk[c] = lnk[q];
                std::copy(nxt[q], nxt[q] + S, nxt[c]);
                for (; p >= 1 && nxt[p][x] == q; nxt[p][x] = c, p = lnk[p]);
                lnk[cur] = lnk[q] = c;
            }
        }
        lst = cur;
    }
};

SAM<N, 26> S;

int main() {
    for (; scanf("%s%d%d", s + 1, &p, &q) == 3; ) {
        n = strlen(s + 1);
        S.clear();
        S.extend(s[1] - 'a');
        f[1] = p;
        for (int i = 2, j = 2, x = 1; i <= n; i++) {
            for (; S.nxt[x][s[i] - 'a'] == 0 && j <= i; ) {
                S.extend(s[j++] - 'a');
                for (; x >= 1 && S.len[S.lnk[x]] >= (i - 1) - j + 1; x = S.lnk[x]);
                if (x == 0) x = 1;
            }
            f[i] = f[i - 1] + p;
            if (j <= i) {
                x = S.nxt[x][s[i] - 'a'];
                f[i] = std::min(f[i], f[j - 1] + q);
            }
        }
        printf("%lld\n", f[n]);
    }
    return 0;
}