题目大意：

求出最多能记住的单词的权值和，要求最大。

记住的规则就是上一个单词是这个单词的子串。

思路分析：

首先得声明这题是数据水了才能用sa做的。

sa的复杂度最多可以达到 Orz（sumlen * sumlen） ...

所以我们sa处理的就是这个串是否是下一个串的子串，如果是就转移方程。

dp[i] = max (dp[i] , dp[j] + val[i])...

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define maxn 350005 #define inf 0x3f3f3f3f using namespace std; int str[maxn]; int sa[maxn],t1[maxn],t2[maxn],c[maxn],n; int bel[maxn]; int st[maxn],sumlen[maxn],val[maxn]; int dp[maxn]; void suffix(int m) { int *x=t1,*y=t2; for(int i=0;i
      
       =0;i--)sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1) { int p=0; for(int i=n-k;i
       
        =k)y[p++]=sa[i]-k; for(int i=0;i
        
         =0;i--)sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(int i=1;i
         
          =n)break; m=p; } } int rank[maxn],height[maxn]; void getheight() { int k=0; for(int i=0;i
          
           i) { dp[bel[sa[j]]]=max(dp[bel[sa[j]]],val[bel[sa[j]]]+dp[i]); } } mlen=inf; for(int j=rank[st[i]]-1;j>0;j--) { mlen=min(mlen,height[j+1]); if(mlen
           
            i) { dp[bel[sa[j]]]=max(dp[bel[sa[j]]],val[bel[sa[j]]]+dp[i]); } } } printf("Case #%d: %d\n",cas++,max(0,*max_element(dp+1,dp+1+N))); } return 0; } /* 1 6 abbab 800 a 1 ab 2 abb 3 baba 5 abbab 8 */