洛谷2408不同字串个数/SPOJ 694/705 （后缀数组SA）-白红宇

洛谷2408不同字串个数/SPOJ 694/705 （后缀数组SA）

阅读量：4497 次

发布时间：2019-06-08

本文共 2490 字，大约阅读时间需要 8 分钟。

真是一个三倍经验好题啊。

我们来观察这个题目，首先如果直接整体计算，怕是不太好计算。

首先，我们可以将每个子串都看成一个后缀的的前缀。那我们就可以考虑一个一个后缀来计算了。

为了方便起见，我们选择按照字典序来一次插入每个后缀，然后每次考虑当前后缀会产生的新串和与之前插入的串重复的串（这里之所以可以这么考虑，是因为如果他会对后面的串产生重复的话，那么会在后面那个串加入的时候计算的）

那么我们考虑，一个排名为\(i\)的后缀，插入之后不考虑重复的话，会新增多少个子串呢？

不难发现是\(n-sa[i]+1\)个（注意后缀的位置编号是从前开始，而后缀的贡献是后面的子串个数。

那么重复的该怎么计算呢？

我们发现重复的部分实际是当前这个后缀和之前的后缀的\(lcp\)部分会重复，而且应该是最大的\(lcp\) （如果取小的会算少，直接求sum会算多）。

而有一个比较经典的性质就是，在字典序\(1到i\)中与\(i\)的\(lcp\)长度最长的，一定是\(i-1\)，这里有两种理解方式，一个是越远差距越大，另一种是越靠前，取\(min\)的范围越大，\(min\)就会可能越小

那么枚举+计算，记得开\(long \ long\)就三倍经验辣

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define mk makr_pair#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}const int maxn = 2e5+1e2;int rk[maxn],sa[maxn];int wb[maxn];int tmp[maxn];char a[maxn];int n;int h[maxn],height[maxn];void getsa(){ int *x=rk,*y=tmp; int s=128; int p=0; for (int i=1;i<=n;i++) x[i]=a[i],y[i]=i; for (int i=1;i<=s;i++) wb[i]=0; for (int i=1;i<=n;i++) wb[x[y[i]]]++; for (int i=1;i<=s;i++) wb[i]+=wb[i-1]; for (int i=n;i>=1;i--) sa[wb[x[y[i]]]--]=y[i]; for (int j=1;p
            
             <<=1) { p=0; for (int i=n-j+1;i<=n;i++) y[++p]=i; for (int i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j; for (int i=1;i<=s;i++) wb[i]=0; for (int i=1;i<=n;i++) wb[x[y[i]]]++; for (int i=1;i<=s;i++) wb[i]+=wb[i-1]; for (int i=n;i>=1;i--) sa[wb[x[y[i]]]--]=y[i]; swap(x,y); p=1; x[sa[1]]=1; for (int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]) ? p : ++p; s=p; } for (int i=1;i<=n;i++) rk[sa[i]]=i; h[0]=0; for (int i=1;i<=n;i++) { h[i]=max(h[i-1]-1,0); while(i+h[i]<=n && sa[rk[i]-1]+h[i]<=n && a[i+h[i]]==a[sa[rk[i]-1]+h[i]]) h[i]++; } for (int i=1;i<=n;i++) height[i]=h[sa[i]];} int t;void init(){ memset(wb,0,sizeof(wb)); memset(rk,0,sizeof(rk)); memset(sa,0,sizeof(sa)); memset(tmp,0,sizeof(tmp)); memset(h,0,sizeof(h)); memset(height,0,sizeof(height));}int main(){ //cin>>t; //while (t--) //{ n=read(); init(); scanf("%s",a+1); getsa(); long long ans=0; for (int i=1;i<=n;i++) { ans=ans+(long long)(n-sa[i]+1)-(long long)h[i];//这里可以理解成我们顺着字典序的顺序，加入每个后缀，将子串看成后缀的前缀 // 而每次加入会产生新的n-sa[i]+1个字串，其中重复的就是和之前的子串的某些lcp，而字典序上，在这个串前面，与某个串lcp最长的应该是i-1那个串（这里可以理解成越往前差距越大） } cout<
             
              <<"\n"; // } return 0;}

转载于:https://www.cnblogs.com/yimmortal/p/10161979.html

你可能感兴趣的文章