tags:后缀自动机

题意

一开始你有一个空串,你有两种操作,一是向这个串的末尾加上任意小写字母,代价为 \(p​\), 二是向这个串的末尾加上这个串的任意一个子串,告诉你最终状态,让你求最少要多少代价才能变成最终状态

题解

用 \(f_i\) 表示变成 \(s[1,i]\) 的最小代价

那么对于第一种操作 \(f_i=f_{i-1}+p\)

对于第二种操作 \(f_i=f_{j-1}+q\), 其中, \(s[j,i]\) 在 \(s[1,j-1]\) 种出现过

第一种很好转移,第二种用后缀自动机维护,由于 \(j\) 是单调的,所以在 \(j\) 向右移时将 \(s_j\) 加入 SAM, 然后维护 \(s[l,r]\) 的节点即可,时间复杂度是 \(O(n)\) 的

#include
    
     #include
     
      #define rep(i,a,b) for(int i=(a);i<=(b);++i)template
      
       inline void rd(T&x){int fl=0,ch;while(ch=getchar(),ch<48||57
       
        
         <58)x=x*10+(ch&15);if(fl)x=-x;}template
         
          inline void pt(T x){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);}template
          
           inline void pt(T x,int ch){pt(x),putchar(ch);}template
           
            inline T max(const T&x,const T&y){return x
            
             
              inline T min(const T&x,const T&y){return x
              
               l-1)&&l<=r){ sam.extend(s[l++]-'a'); while(p&&sam.len[sam.fa[p]]>=r-l)p=sam.fa[p]; if(!p)p=1; } p=sam.ch[p][c]; while(p&&sam.len[sam.fa[p]]>=r-l+1)p=sam.fa[p]; if(!p)p=1; if(l<=r){ f[r]=min(f[r],f[l-1]+w2); } } pt(f[n],'\n'); } return 0;}