C++(g++ 7.5.0) 解法, 执行用时: 60ms, 内存消耗: 47436K, 提交时间: 2022-08-01 02:11:51

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10,M=26;
char s[N];
int n,fa[N],go[N][M],mxl[N],last,tot,p,q;
ll dp[N];
int newnode(int l) {int u=++tot; mxl[u]=l,memset(go[u],0,sizeof go[u]); return u;}
void add(int ch) {
    int p=last,np=last=newnode(mxl[p]+1);
    for(; p&&!go[p][ch]; p=fa[p])go[p][ch]=np;
    if(!p)fa[np]=1;
    else {
        int q=go[p][ch];
        if(mxl[q]==mxl[p]+1)fa[np]=q;
        else {
            int nq=newnode(mxl[p]+1);
            memcpy(go[nq],go[q],sizeof go[q]);
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for(; p&&go[p][ch]==q; p=fa[p])go[p][ch]=nq;
        }
    }
}
int main() {
    while(scanf("%s%d%d",s,&p,&q)==3) {
        n=strlen(s),tot=0;
        last=newnode(0);
        memset(dp,0x3f,sizeof dp),dp[0]=0;
        for(int i=0,j=0,u=1; i<n; add(s[i]-'a'),++i) {
            for(; j<n; u=go[u][s[j]-'a'],++j) {
                for(; !go[u][s[j]-'a']&&fa[u]&&mxl[fa[u]]>=j-i; u=fa[u]);
                if(!go[u][s[j]-'a'])break;
            }
            dp[i+1]=min(dp[i+1],dp[i]+p),dp[j]=min(dp[j],dp[i]+q);
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}

C++ 解法, 执行用时: 60ms, 内存消耗: 45664K, 提交时间: 2022-07-11 20:56:49

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
const int M = 26;
struct state { int len, fa, next[M]; }st[N];
int tot = 1, last = 1;

void extend(int c)
{
    int cur = ++tot;
    st[cur].len = st[last].len + 1;
    int p = last; last = cur;
    while (p && !st[p].next[c])
        st[p].next[c] = cur, p = st[p].fa;
    if (!p) return st[cur].fa = 1, void();
	int q = st[p].next[c];
	if (st[p].len + 1 == st[q].len) st[cur].fa = q;
	else
	{
		int clone = ++tot;
		st[clone] = st[q];
		st[clone].len = st[p].len + 1;
		while (p && st[p].next[c] == q)
			st[p].next[c] = clone, p = st[p].fa;
		st[q].fa = st[cur].fa = clone;
	}
}

char s[N];
ll dp[N];
int main()
{
    int a, b;
    scanf("%s%d%d", s + 1, &a, &b);
	int n = strlen(s + 1), u = 1;
	for (int i = 1, j = 0; i <= n; i++)
	{
		dp[i] = dp[i - 1] + a;
		int c = s[i] - 'a';
		while (1)
		{
			while (u != 1 && st[st[u].fa].len + 1 >= i - j) u = st[u].fa;
			if (st[u].next[c]) break;
			else extend(s[++j] - 'a');
		}
		u = st[u].next[c];
		dp[i] = min(dp[i], dp[j] + b);
	}
	cout << dp[n];
    return 0;
}