codeforces#1120C. Compress String（dp+后缀自动机）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5000+10;
char S[maxn];
int n,a,b;
struct suffixautomation
{
    int mp[maxn*2][30],fa[maxn*2],ed,ct,len[maxn*2],minpos[maxn*2],deg[maxn*2],pos[maxn][maxn];
    int dp[maxn];
    suffixautomation(){ed=ct=1;}
    inline void ins(int c,int pos)
    {
        int p=ed;ed=++ct;minpos[ed]=pos;len[ed]=pos;//先初始化size和len
        for(;p&&mp[p][c]==0;p=fa[p]){mp[p][c]=ed;}//然后顺着parent树的路径向上找
        if(p==0){fa[ed]=1;return;}int q=mp[p][c];//case1
        if(len[p]+1==len[q]){fa[ed]=q;return;}//case2
        len[++ct]=len[p]+1;//case 3
        for(int i=1;i<=26;i++){mp[ct][i]=mp[q][i];}
        fa[ct]=fa[q];fa[q]=ct;fa[ed]=ct;
        for(int i=p;mp[i][c]==q;i=fa[i]){mp[i][c]=ct;}
    }
    void solve(){
        for(int i=1;i<=n;i++){
            int now=1;
            for(int j=i;j<=n;j++){
                int v=S[j]-‘a‘+1;
                now=mp[now][v];
                pos[i][j]=now;
            }
        }
        for(int i=1;i<=ct;i++)deg[fa[i]]++;
        queue<int>que;
        for(int i=1;i<=ct;i++)if(deg[i]==0)que.push(i);
        while(que.size()){
            int x=que.front();
            int y=fa[x];
            que.pop();
            minpos[y]=min(minpos[x],minpos[y]);
            deg[y]--;
            if(deg[y]==0)que.push(y);
        }
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+a;
            for(int j=2;j<=i;j++){
                if(minpos[pos[j][i]]<j){
                    dp[i]=min(dp[i],dp[j-1]+b);
                    break;
                }
            }
        }
        printf("%d\n",dp[n]);

    }
}sam;
int main()
{
    scanf("%d %d %d",&n,&a,&b);
    scanf("%s",S+1);
    for(int i=0;i<maxn*2;i++)sam.minpos[i]=1e9;
    for(int i=1;i<=n;i++)sam.ins(S[i]-‘a‘+1,i);
    sam.solve();
    return 0;
}