「题解」Typewriter

一道很好的SAM+DP综合题，虽然说坑点也很多……

原题链接

考虑DP。设 $f[i]$ 为考虑前 $i$ 个位置的答案，应当有转移 $f[i] = \min f[i - 1] + p, f[l]+q$ ，其中 $l$ 满足 $s[l+1:r]\subseteq s[1:l]$ 。$f[]$ 显然是不降的，那么我们应取最小的 $l$ 。

考虑 $r\to r + 1$ ，容易发现 $l$ 是不降的；那么对 $s[1:l]$ 建立SAM，每次尝试扩展 $s[r+1]$，如果不行则令 $l\to l + 1$，即可找到最小的 $l$。维护当前的 $s[l+1:r]$ 对应在SAM上的路径，则可 O(1) 做到删除该路径上的第一个字符 $s[l+1]$ ，然后再扩展出$s[r+1]$即可。

小细节：当SAM在extend()的时候，若该路径的终点 $d$ 被拆成了 $v,d’$ 两个节点，且$\text{nxt}[d’]=v$，则应当将路径的终点变换为 $v$，否则维护的路径就被破坏了。
HDU不给数据，然后上面那个坑点卡了我一晚上…

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 2e5 + 5;

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

class SAM{
  public: int nxt[CN << 1], son[CN << 1][26], len[CN << 1], sz, lst, cur, l;
    void init(int n){
        for(int i = 0;i < (n << 1);i++) for(int j = 0;j < 26;j++) son[i][j] = 0; // 题目卡memset()
        sz = 1, lst = cur = l = len[0] = 0, nxt[0] = -1;
    }
    void et(int c){
        int u = sz++, p = lst;
        lst = u, len[u] = len[p] + 1;
        while(p != -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
        if(p == -1) return (void)(nxt[u] = 0);
        int d = son[p][c];
        if(len[d] == len[p] + 1) return (void)(nxt[u] = d);
        int v = sz++; 
        if(d == cur) cur = v; // 坑点
        len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[d] = nxt[u] = v;
        for(int i = 0; i < 26; i++) son[v][i] = son[d][i];
        while(p != -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
    }
    void del() {if(nxt[cur] != -1 && --l == len[ nxt[cur] ]) cur = nxt[cur];}   // delete
    bool rd(int c) {return son[cur][c] ? cur = son[cur][c], l++, true : false;} // read
}D;

int main()
{  
    freopen("_in.in", "r", stdin);
    // freopen("wa.out", "w", stdout);

    while(cin >> (s + 1)){
        n = strlen(s + 1), scanf("%lld%lld", &p, &q), D.init(n);

        int l = 1; D.et(s[1] - 'a'), prv[1] = 0;
        for(int i = 2; i <= n; i++){
            bool flag = true;
            while(!D.rd(s[i] - 'a')){
                if(l + 1 == i) {flag = false; break;}
                D.del(), D.et(s[++l] - 'a');
            }
            prv[i] = flag ? l : 0;
            if(!flag) D.et(s[++l] - 'a');
        }

        f[1] = p;
        for(int i = 2;i <= n;i++)
            if(prv[i]) f[i] = min(f[i - 1] + p, f[ prv[i] ] + q);
            else f[i] = f[i - 1] + p;

        printf("%lld", f[n]), puts("");
    }
}