题意：给定一个由小写字母组成的字符串，每次可以花费p在串后加上任意一个字母，花费q在串后复制一个当前串的子串，问生成字符串的最小花费
n<=2e5,1<=p,q<2^31
思路：
SAM上每个结点表示的串长度为[st[F[p]]+1,st[p]]，如果长度不符合当前i,j的要求，比如复制的时候长度小于当前的一半或者长度大于[j+1,i]就暴力往上跳parent
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 typedef pair<ll,int>P; 11 #define N 500010 12 #define M 210000 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pi acos(-1) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 20 #define lowbit(x) x&(-x) 21 #define Rand (rand()*(1<<16)+rand()) 22 #define id(x) ((x)<=B?(x):m-n/(x)+1) 23 #define ls p<<1 24 #define rs p<<1|1 25 26 const ll MOD=1e9+7,inv2=(MOD+1)/2; 27 double eps=1e-6; 28 ll INF=1ll<<62; 29 ll inf=5e13; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 char s[N]; 34 int ch[N][26],st[N],F[N],p,np,q,nq,cnt,t; 35 ll dp[N],A,B; 36 37 int read() 38 { 39 int v=0,f=1; 40 char c=getchar(); 41 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 42 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 43 return v*f; 44 } 45 46 struct sam 47 { 48 void extend(int x) 49 { 50 p=np; 51 st[np=++cnt]=st[p]+1; 52 while(p&&!ch[p][x]) 53 { 54 ch[p][x]=np; 55 p=F[p]; 56 } 57 58 if(!p) F[np]=1; 59 else if(st[p]+1==st[q=ch[p][x]]) F[np]=q; 60 else 61 { 62 st[nq=++cnt]=st[p]+1; 63 memcpy(ch[nq],ch[q],sizeof ch[q]); 64 F[nq]=F[q]; 65 F[q]=F[np]=nq; 66 while(p&&ch[p][x]==q) 67 { 68 ch[p][x]=nq; 69 p=F[p]; 70 } 71 } 72 } 73 74 void cancel(int len) 75 { 76 while(t&&st[F[t]]>=len) t=F[t]; 77 if(!t) t=1; 78 } 79 80 void trans(int len,int x) 81 { 82 t=ch[t][x]; 83 if(!t) t=1; 84 cancel(len); 85 } 86 87 }sam; 88 89 void solve() 90 { 91 int n=strlen(s); 92 //rep(i,1,n) dp[i]=INF; 93 94 cnt=np=t=1; 95 sam.extend(s[0]-'a'); 96 dp[0]=A; 97 int j=1; 98 rep(i,1,n-1) 99 { 100 dp[i]=dp[i-1]+A; 101 int x=s[i]-'a'; 102 while((!ch[t][x]||i-j+1>(i+1)/2)&&j<=i) 103 { 104 sam.extend(s[j++]-'a'); 105 sam.cancel(i-j); 106 107 } 108 sam.trans(i-j+1,x); 109 if(j<=i) dp[i]=min(dp[i],dp[j-1]+B); 110 } 111 112 rep(i,1,cnt) 113 { 114 rep(j,0,25) ch[i][j]=0; 115 F[i]=st[i]=0; 116 } 117 printf("%lld\n",dp[n-1]); 118 } 119 120 int main() 121 { 122 //freopen("1.in","r",stdin); 123 //freopen("1.out","w",stdout); 124 while(scanf("%s%lld%lld",s,&A,&B)!=EOF) 125 { 126 solve(); 127 } 128 return 0; 129 }