题意就是让你拼字符串
在后面添加任意一个字符的代价是p,将原串的子串复制到后面的代价是q，
怎么做呢
设DP[i]代表着拼成前i个字符的 最小花费
我们假设 在  j--i 的字符串 是 0--j-1部分的子串
那么有dp[i]=min(  dp[i-1]+p  ,   dp[j-1]+q  )
利用后缀自动机维护  j  的位置

cur 是当前0--j-1内子串的状态
 
每次都对第i个字符进行匹配，如果匹配到，就跳转到下一个状态，继续匹配第i+1个字符
如果匹配失败，那就将第j个字符加入自动机，同时j++
因为随着j的增大，j--i的子串长度会变短，前缀会一直去掉，所以我们就取跳到fa[cur],改变匹配的位置
保证了最优解  注意一些  i-j  i-j+1的细节 

 

#include<bits/stdc++.h>  using namespace std; typedef long long ll; const int maxn=2e5+5;  struct SAM {int trans[maxn<<1][26],slink[maxn<<1],maxlen[maxn<<1];  int last,now,root,len;  void newnode(intv)
    { maxlen[++now]=v;  }void extend(intc)
    {
        newnode(maxlen[last]+1);  int p=last,np=now;  while(p&&!trans[p][c])
        { trans[p][c]=np;  p=slink[p];  } if(!p) slink[np]=root;  else  { intq=trans[p][c];  if(maxlen[p]+1!=maxlen[q])
            {
                newnode(maxlen[p]+1);  int nq=now;  memcpy(trans[nq],trans[q],sizeof(trans[q]));  slink[nq]=slink[q];  slink[q]=slink[np]=nq;  while(p&&trans[p][c]==q)
                { trans[p][c]=nq;  p=slink[p];  }
            }else  slink[np]=q;  } last=np;  }void build()
    { root=last=now=1;  for(inti=0;i<(maxn<<1);i++)
            memset(trans[i],0,sizeof(trans[i]));  memset(slink,0,sizeof(slink));  memset(maxlen,0,sizeof(maxlen));  }
}sam;  char s[maxn]; ll dp[maxn]; int main()
{ while(scanf("%s",s)!=EOF)
    { intp,q;  scanf("%d%d",&p,&q);  sam.build();  sam.len=strlen(s);  int cur=1;  dp[0]=p;  int j=1;  sam.extend(s[0]-'a');  for(inti=1;i<sam.len;i++)
        {
            dp[i]=dp[i-1]+p;  while((!sam.trans[cur][s[i]-'a']||(i-j+1)>j))
            {
                sam.extend(s[j]-'a');j++;  while(cur&&sam.maxlen[sam.slink[cur]]>=(i-j))
                {
                    cur=sam.slink[cur];  } if(!cur)
                    cur=1;  }
            cur=sam.trans[cur][s[i]-'a'];  while(cur&&sam.maxlen[sam.slink[cur]]>=(i-j+1))
            {
                cur=sam.slink[cur];  } if(!cur)
                cur=1;  if(i>=j)
                dp[i]=min(dp[i],dp[j-1]+q);  }
        printf("%lld\n",dp[sam.len-1]);  }return 0; }