[學習筆記]字尾數組

參考：

字尾數組最詳細講解

上面一篇是轉載這一篇的：

字尾數組學習筆記

一、

字尾：suff(i)，字尾要排序

sa[i]，排名為i的字尾開始位置

rk[i]，i開始位置的字尾的排名。

rk[sa[i]]=i,sa[rk[i]]=i

字尾要排序。

暴力排序:O(n^2logn)

可以利用倍增+基數排序優化到O(nlogn)

以下圖檔轉載自：字尾數組最詳細講解

為了避免常數過大，不能用vector當桶來用。

以及各種優化具體代碼實作在下面。

二、

不能光排序。沒有用。

設LCP(i,j)為，排名為i和排名為j的字尾的最長公共字首長度。（注意i,j是排名）

即：LCP(suff[sa[i]],suff[sa[j]])（這個LCP是最長公共字首的意思）

性質：

LCP(i,j)=LCP(j,i)

LCP(i,i)=len(sa[i])=n-sa[i]+1

這個太平凡了。

2.LCP(i,k)=min(LCP(i,j),LCP(j,k)) 對于任意1<=i<=j<=k<=n，都滿足

證明：

設p=min(LCP(i,j),LCP(j,k))

那麼有：LCP(i,j)>=p,LCP(j,k)>=p

那麼必然有LCP(i,k)>=p

假如LCP(i,k)=q>p

那麼有：s[i+p+1]=s[k+p+1],并且s[i+p+1]!=s[j+p+1],s[j+p+1]!=s[k+p+1]

那麼，i,k的字典序顯然更接近。不滿足：1<=i<=j<=k<=n

是以LCP(i,k)<=p

是以，LCP(i,k)=p

證畢

3.LCP(i,k)=min(LCP(j,j-1)) 對于所有的1<i<=j<=k<=n取一個min

有：LCP(i,k)=min(LCP(i,i+1),LCP(i+1,k))，然後不斷拆下去，即可證明。

三、LCP求法

根據以上性質，

人們設計了：height[i]表示，LCP(suff[sa[i]],suff[sa[i-1]])

設h[i]表示，height[rk[i]]

關鍵性質：

h[i]>=h[i-1]-1；

設sa[rk[i-1]-1]=k

h[i-1]=p

那麼有：suff[k],suff[i-1]的前p位相同。

1.s[k]!=s[i-1]

即p=0，顯然成立。

2.s[k]=s[i-1]

suff[k],suff[i-1]的前p位相同。

是以，suff[k+1],suff[i]的前p-1位相同，

LCP(suff[i],suff[k+1])=p-1

由于k+1對于i位置來講，suff[k+1]比較平凡，不如suff[sa[rk[i]-1]]和suff[i]相似度更大。

是以，一定有：h[i]>=p-1=h[i-1]-1

有了這個性質，就可以算出height來了。或者h

然後利用LCP(i,k)=min(LCP(j,j-1)) 對于所有的1<i<=j<=k<=n取一個min

這一條就是LCP(i,k)=min(height[j])對于所有的1<i<j<=k<=n取一個min

經常求出height之後，用RMQ等可以直接找到LCP(i,k)

代碼：

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1e6+6;
char s[N];
int n,m;
int x[2*N],y[2*N],sa[N];//不開兩倍，下面求x的時候會RE（當然求x的時候，對sa[i]+k和n+1取min也可以，總之要是0 
int c[N],num;
int rk[N],hei[N];
void get_SA(){
    m=122;//m表示剩下的排名種類個數 
    for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];//c是桶，x是第一關鍵字 
    for(reg i=2;i<=m;++i) c[i]+=c[i-1];//c做字首和，得到第一關鍵字為x的字尾排名最少是多少。 
    for(reg i=1;i<=n;++i) sa[c[x[i]]--]=i;//處理目前sa 
    for(reg k=1;k<=n;k<<=1){
        num=0;
        for(reg i=n-k+1;i<=n;++i) y[++num]=i;//y[i]表示第二關鍵字排在 第i位的字尾，起始位置是多少 
        //這裡直接把第二關鍵字是0的放進去，因為它們肯定在最前面 
        for(reg i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;//如果滿足sa[i]>k，就有i會作為sa[i]-k的第二關鍵字。加進去 
        for(reg i=1;i<=m;++i) c[i]=0;//清空桶 
        for(reg i=1;i<=n;++i) ++c[x[i]];//累計第一關鍵字個數 
        for(reg i=2;i<=m;++i) c[i]+=c[i-1];//字首和 
        for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;//處理目前sa，注意倒序這樣第一關鍵字相同的，第二關鍵字一定升序排列 
        swap(x,y);//複制一下，便于後面處理x[i] 
        num=1;
        x[sa[1]]=1;
        for(reg i=2;i<=n;++i) 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_HEI(){
    for(reg i=1;i<=n;++i) rk[sa[i]]=i;//刷rank 
    int k=0;
    for(reg i=1;i<=n;++i){
        if(rk[i]==1) continue;//h[sa[1]]=0 
        if(k) --k;//h[i]>=h[i-1]-1
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;//暴力比對，因為每次k最多-1，k最多是n，是以複雜度O(n) 
        hei[rk[i]]=k;
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    get_SA();
    for(reg i=1;i<=n;++i){
        printf("%d ",sa[i]);
    }return 0;
}

}
int main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/11/14 21:24:52
*/

四、例題

P2408 不同子串個數

子串是所有字尾的所有字首

對于出現兩次的子串，必然起始位置的lcp大于等于長度。

某個子串每多出現一次，就會在某個hei[i]中出現。

是以，個數就是：n*(n-1)/2+n-∑hei[i]

每個出現多次的子串，都一定會被減掉多餘的次數次。

更好的考慮方法是：

每個字尾貢獻的字首：就是n-sa[i]+1-height[i]

總共的字首個數，減去和上一個排名的相同的字首（即子串）個數。

剩下的一定都是之前沒有出現過的。

是以所有之前出現出現過的都減去了。

當然，這個式子∑一下就是上面的那個。

BZOJ 4310: 跳蚤

求出本質不同的子串個數。

二分排名mid

從小到大枚舉sa，求出第mid大的本質不同的子串出現位置。

具體來講，每個位置的sa貢獻的不同子串個數是：n-sa[i]+1-height[i]

而且新出現的一定是沒有出現的最小的那幾個。

是以，如果貢獻的子串小于k個，就k-=貢獻，繼續找。否則就是剩下的第k個位置。

（當然，可以對貢獻做一個字首和，然後二分即可。O(n)->O(logn)）

之後貪心砍

從後往前，由于是子串的最大子串，是以，每當得到一個子串比第mid個子串大，必須砍掉。

不能不砍，而如果在之前砍的話，留下的部分字典序一定更大。不優。

是以貪心正确。

比較兩個串字典序大小，利用字尾數組直接RMQ求LCP即可。

注意，二分的mid是long long級别。re也要開long long

[學習筆記]字尾數組

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1e5+5;
int n,m,p;
char s[N];
int sa[N],rk[N],hei[N];
int x[2*N],y[2*N];
int c[N],num;
void SA(){
    m=230;
    for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];
    for(reg i=2;i<=m;++i) c[i]+=c[i-1];
    for(reg i=n;i>=1;--i) sa[c[x[i]]--]=i;
    for(reg k=1;k<=n;k<<=1){
        num=0;
        for(reg i=n-k+1;i<=n;++i) y[++num]=i;
        for(reg i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;
        for(reg i=1;i<=m;++i) c[i]=0;
        for(reg i=1;i<=n;++i) ++c[x[i]];
        for(reg i=2;i<=m;++i) c[i]+=c[i-1];
        for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        num=1;x[sa[1]]=1;
        for(reg i=2;i<=n;++i){
            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 HEI(){
    for(reg i=1;i<=n;++i) rk[sa[i]]=i;
    int k=0;
    for(reg i=1;i<=n;++i){
        if(rk[i]==1) continue;
        if(k) --k;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
        hei[rk[i]]=k;
    }
}
int f[N][20];
int lg[N];
int LCP(int i,int j){
    if(i>j) swap(i,j);
    if(i==j) return n-sa[i]+1;
    int len=j-i;
    int ret=min(f[i+1][lg[len]],f[j-(1<<lg[len])+1][lg[len]]);
    return ret;
}
bool cmp(int s1,int d1,int s2,int d2){//s1<=s2 return 1
    int lcp=LCP(rk[s1],rk[s2]);
    //cout<<" lcp "<<lcp<<endl;
    int l1=d1-s1+1,l2=d2-s2+1;
    if(l1<=l2){
        if(lcp>=l1) return true;
        if(lcp<l1) return s[s1+lcp]<=s[s2+lcp];
    } 
    else{
        if(lcp>=l2) return false;
        if(lcp<l2) return s[s1+lcp]<=s[s2+lcp];
    }
}
ll l,r;
int st,nd;
bool che(ll mid){
    //cout<<" mid ------------------------"<<mid<<endl;
    int tot=0;
       st=1,nd=0;
    ll re=mid;
    while(re>n-sa[st]+1-hei[st]){
        re-=n-sa[st]+1-hei[st];
        ++st;
    }
    nd=sa[st]+hei[st]-1+re;
    st=sa[st];
    //cout<<" st "<<st<<" nd "<<nd<<endl;
    int rr=n;
    for(reg i=n;i>=1;--i){
        if(tot>p) return false;
        while(i>=1&&cmp(i,rr,st,nd)) --i;
        ++tot;
        rr=i;
        //cout<<" tot "<<tot<<" : "<<i<<" "<<rr<<endl;
        ++i;
    }
    return tot<=p;
}
int main(){
    scanf("%d",&p);
    scanf("%s",s+1);
    n=strlen(s+1);
    SA();HEI();
    for(reg i=1;i<=n;++i) {
        lg[i]=(i>>(lg[i-1]+1))?lg[i-1]+1:lg[i-1];
        f[i][0]=hei[i];
        r+=n-sa[i]+1-hei[i];
    }
    for(reg j=1;(1<<j)<=n;++j){
        for(reg i=1;i+(1<<j)-1<=n;++i){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    l=1;
    ll ans=0;
//    for(reg i=1;i<=n;++i){
//        cout<<i<<" : "<<rk[i]<<" "<<sa[i]<<" "<<hei[i]<<endl;
//    }
//    cout<<" judge "<<cmp(4,5,1,4)<<endl;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(che(mid)){
            ans=mid;r=mid-1;            
        }
        else l=mid+1;
    }
    ans=che(ans);
    for(reg i=st;i<=nd;++i) putchar(s[i]);
    return 0;
}

}
int main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/11/15 21:46:33
*/

跳蚤

P2852 [USACO06DEC]牛奶模式Milk Patterns

對于出現k次的子串，考慮sa序列，枚舉最長子串的出現位置中排名最靠後的位置的起始位置，為了找到最長的子串，必然找前面連續k個位置所代表的字尾，

不斷求LCP，也就是求LCP(i,i-k+1)，就是這個子串長度

單調隊列優化即可。

[學習筆記]字尾數組

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1000000+5;
int s[N];
int n,m,p;
int sa[N],rk[N],hei[N],c[N];
int x[2*N],y[2*N];
int num;
void SA(){
    num=0;
    m=1000000;
    for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];
    for(reg i=2;i<=m;++i) c[i]+=c[i-1];
    for(reg i=1;i<=n;++i) sa[c[x[i]]--]=i;
    for(reg k=1;k<=n;k<<=1){
        num=0;
        for(reg i=n-k+1;i<=n;++i) y[++num]=i;
        for(reg i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;
        for(reg i=1;i<=m;++i) c[i]=0;
        for(reg i=1;i<=n;++i) ++c[x[i]];
        for(reg i=2;i<=m;++i) c[i]+=c[i-1];
        for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        num=1;
        x[sa[1]]=1;
        for(reg i=2;i<=n;++i){
            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;
    }
//    for(reg i=1;i<=n;++i){
//        cout<<i<<" : "<<sa[i]<<endl;
//    }
}
void HEI(){
    for(reg i=1;i<=n;++i) rk[sa[i]]=i;
    int k=0;
    for(reg i=1;i<=n;++i){
        if(rk[i]==1) continue;
        if(k) --k;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
        hei[rk[i]]=k;
    }
}
int q[N],l,r;
int wrk(){
    l=1;
    int ret=0;
    for(reg i=2;i<=p-1;++i){
        while(l<=r&&hei[q[r]]>=hei[i]) --r;
        q[++r]=i;
    }
    //if(l<=r) ret=max(ret,hei[q[l]]);
    for(reg i=p;i<=n;++i){
        while(l<=r&&hei[q[r]]>=hei[i]) --r;
        q[++r]=i;
        while(l<=r&&q[l]<i-p+2)++l;
        if(l<=r) ret=max(ret,hei[q[l]]);
    }
    return ret;
}
int main(){
    rd(n);rd(p);
    for(reg i=1;i<=n;++i) rd(s[i]);
    SA();HEI();
    int ans=wrk();
    printf("%d\n",ans);
    return 0;
}

}
int main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/11/15 8:52:42
*/

牛奶模式

P3181 [HAOI2016]找相同字元

另一篇：[HAOI2016]找相同字元

P2178 [NOI2015]品酒大會

求出height，顯然要先求出LCP=r的個數以及最大值。然後字首處理一下。

求LCP=r的個數及最大值：

1.分治。類似于“找相同字元”那個題，注意，mid左邊選擇一個最值，mid右邊選擇一個最值。維護兩個指針掃過的位置的最值。

最後合并即可。

[學習筆記]字尾數組

#include<bits/stdc++.h>
#define reg register int
#define int long long 
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=300000+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m;
char s[N];
ll a[N];
struct node{
    ll ans;
    ll mx;
    void init(){
        ans=0;mx=-inf;
    }
    node operator +(const node &b){
        node c;c.init();
        c.ans=ans+b.ans;
        c.mx=max(mx,b.mx);
        return c;
    }
}b[N];
int sa[N],rk[N],hei[N];
int y[2*N],x[2*N];
int c[N],num;
void SA(){
    m=122;
    for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];
    for(reg i=2;i<=m;++i) c[i]+=c[i-1];
    for(reg i=n;i>=1;--i) sa[c[x[i]]--]=i;
    for(reg k=1;k<=n;k<<=1){
        num=0;
        for(reg i=n-k+1;i<=n;++i) y[++num]=i;
        for(reg i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;
        for(reg i=1;i<=m;++i) c[i]=0;
        for(reg i=1;i<=n;++i) ++c[x[i]];
        for(reg i=2;i<=m;++i) c[i]+=c[i-1];
        for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        num=1;x[sa[1]]=1;
        for(reg i=2;i<=n;++i){
            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 HEI(){
    for(reg i=1;i<=n;++i) rk[sa[i]]=i;
    int k=0;
    for(reg i=1;i<=n;++i){
        if(rk[i]==1) continue;
        if(k) --k;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
        hei[rk[i]]=k;
    }
}
void divi(int l,int r){
//    cout<<" divi "<<l<<" and "<<r<<" ---------------------------"<<endl;
    if(l==r) return;
    int mid=(l+r)/2;
//    cout<<" mid "<<mid<<endl;
    ll mxl=-inf,mil=inf;
    ll mxr=-inf,mir=inf;
    
    int mi=0x3f3f3f3f;
    int ptr=mid+1;
    for(reg i=mid+1;i<=r;++i){
        mi=min(mi,hei[i]);
        while(ptr>=l+1&&hei[ptr]>=mi){
            //tmp.upda(a[sa[ptr-1]]);
            mil=min(mil,a[sa[ptr-1]]);
            mxl=max(mxl,a[sa[ptr-1]]);
            ptr--;
        }
        b[mi].ans+=(mid-ptr+1);
        if(mil!=inf)b[mi].mx=max(b[mi].mx,mil*a[sa[i]]);
        if(mxl!=-inf)b[mi].mx=max(b[mi].mx,mxl*a[sa[i]]);
        
//        cout<<" ii "<<i<<" ptr "<<ptr<<endl;
//        for(reg i=0;i<=2;++i){
//            cout<<i<<" : "<<b[i].val[0]<<" "<<b[i].val[1]<<" || "<<b[i].val[2]<<" "<<b[i].val[3]<<endl;
//        }
    }
//    cout<<" half "<<endl;
    
    mi=inf;
    ptr=mid;
    for(reg i=mid;i>=l;--i){
        mi=min(mi,hei[i+1]);
        while(ptr+1<=r&&hei[ptr+1]>mi){
            //tmp.upda(a[sa[ptr+1]]);
            mir=min(mir,a[sa[ptr+1]]);
            mxr=max(mxr,a[sa[ptr+1]]);
            ++ptr;
        }
        b[mi].ans+=(ptr-mid);
        if(mir!=inf)b[mi].mx=max(b[mi].mx,mir*a[sa[i]]);
        if(mxr!=-inf)b[mi].mx=max(b[mi].mx,mxr*a[sa[i]]);
    }
//    cout<<" end "<<endl;
//    for(reg i=0;i<=2;++i){
//        cout<<i<<" : "<<b[i].ans<<" "<<b[i].mx<<endl;
//    }
    divi(l,mid);
    divi(mid+1,r);
}
int main(){
    scanf("%lld",&n);
    scanf("%s",s+1);
    for(reg i=1;i<=n;++i)scanf("%lld",&a[i]);
    SA();HEI();
//    for(reg i=1;i<=n;++i){
//        cout<<i<<" "<<sa[i]<<" "<<hei[i]<<endl;
//    }
//    cout<<"--------------------------------"<<endl;
//    
//    cout<<"hei : ";
//    for(reg i=1;i<=n;++i){
//        cout<<hei[i]<<" ";
//    }cout<<endl;
//    cout<<"a[i]: ";
//    for(reg i=1;i<=n;++i){
//        cout<<a[i]<<" ";
//    }cout<<endl;
//    cout<<" sa : ";
//    for(reg i=1;i<=n;++i){
//        cout<<sa[i]<<" ";
//    }cout<<endl;
//    
    for(reg i=0;i<=n;++i)b[i].init();
    divi(1,n);
    for(reg i=n-1;i>=0;--i){
        b[i]=b[i]+b[i+1];
    }
    for(reg i=0;i<=n-1;++i){
        if(b[i].mx==-inf) b[i].mx=0;
        printf("%lld %lld\n",b[i].ans,b[i].mx);
    }
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/11/15 15:54:36
*/

品酒大會

2.并查集。按照height排序，每次合并i,i+1兩個排名所代表的字元串集合。設lcp長度為k，兩邊的集合兩兩組合，lcp一定都為k。

把兩棵樹的size相乘，加入ans[k][0]。每個并查集維護集合内的a[sa[i]]的最大值和最小值，然後ans[k][1]=max(ans[k][1],mi1*mi2,mx1*mx2)

本質是考慮兩個要求LCP的i，j，取得min的位置在哪裡。在取得min的位置的那裡，就會合并這兩個集合并且統計答案。

3.SAM做法

利用Parent樹DP，類似“差異”一題。對反串建SAM，在LCA處統計LCP個數以及最大值，最小值。然後按照len從後往前處理一下即可。

最後都要字首處理一下。

五、總結

字尾數組可以對一個串求出height，

就可以快速支援查找i,j位置開始的lcp長度。即LCP(rk[i],rk[j])，然後用RMQ即可優化。

和區間問題比較像。但是不是直覺地在原始字元串上處理區間，而是對sa序列進行區間處理。

由于是區間，又是找一個最小值，是以可以利用到的方法就比較多了。

[學習筆記]字尾數組

繼續閱讀

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

查找檔案中的字元串

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希