后缀数组

后缀数组学习

后缀数组学习博客

代码

/*made in mrd*/
#include
using namespace std;
const int N=2e6+10;
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define fi first
#define se second
#define lu u<<1
#define ru u<<1|1
#define pb push_back
#define bug1(x) cout<
#define bug3(x,y,z) cout<k) y[++num]=sa[i]-k;
            //上一层循环中按照第一关键字的排名的下标已经存在sa数组中
            //按从小到大顺序枚举sa数组可保证按照第一关键字从小到大
            //所有起始下标超过k才存在第二关键字
            //将所有存在第二关键字的后缀存储在y数组中，此时是按i + k的第一关键字，下标要-k 
        }
        //将计数数组清空
        for(int i=1;i<=m;++i) c[i]=0;
        for(int i=1;i<=n;++i) c[x[i]]++;
        for(int i=2;i<=m;++i) c[i]+=c[i-1];

        for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        //y数组存储的是按照第二关键字从小到大排序后的后缀的起始下标 
        //i从大到小枚举即可保证按照第一关键字排序后依然是按照第二关键字排序后的相对顺序不变 
        swap(x,y);
        //将所有后缀离散化
        x[sa[1]]=1,num=1;
         //此时y存储的是从i开始的后缀的第一关键字 
        for(int i=2;i<=n;++i){
            //若当前后缀和排名前一位的后缀第一关键字和第二关键字相同则离散化后的数值相同，否则+1
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        }
        if(num==n) break;
        m=num;
    }
}

void get_height(){
    for(int i=1;i<=n;++i) rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;++i){
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
        height[rk[i]]=k;
    }
}
signed main() {
    cin>>n;
    cin>>s+1;
    m=122;
    get_sa();
    get_height( );
    int top=0;
    stk[0]=1;
    for(int i=2;i<=n;i++)
    {
        while(top&&height[stk[top]]>=height[i])
        {
            res-=(stk[top]-stk[top-1])*height[stk[top]];
            top--;
        }
        res+=(i-stk[top])*height[i],stk[++top]=i;
        ans[sa[i]]+=res;
    }
    res=0;
    top=0;
     stk[0]=n+1;
    for(int i=n;i>=1;--i){
        ans[sa[i]]+=res+n-sa[i]+1;
        if(i==1) continue;
        while(top && height[stk[top]]>=height[i]){
            res-=1ll*(stk[top-1]-stk[top])*height[stk[top]];
            top--;
        }
        res+=1ll*(stk[top]-i)*height[i],stk[++top]=i;
    }
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ |   │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│  '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/

练习题

F - Common Prefixes

代码同上