后缀数组学习笔记

首先定义:

rank[i]为S[i..n]这个后缀是所有后缀里第几大的。

sa[i]为第i大的后缀是哪一个

因为后缀不可能相等,所以rank[i]和sa[i]唯一,且满足sa[rank[i]]=i

我们可以通过类似多关键字排序+构造Sparse Table的方法使构造这两个数组的时间复杂度为O(nlgn)

注意中间过程用基数排序,否则用qsort的话会变成O(n(lgn)^2)

构造完这个,我们还应该加一个height数组,height[i]表示lcp(i-1,i)。

其中i表示排名,即rank[sa[i]]=i

这样就相当于后缀树中两个相邻节点的lca了。

至于如何构造height[i],这里有我写的code。

其中使用了一个定理:

height[i]>=height[sa[i]-1]-1(看懂什么意思以后,证明显然)

使用这个定理以后构造height的复杂度降到了O(n)

void lcp(){
     memset(height,0,sizeof(height));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st,j,k;
         st=max(height[rank[i-1]]-1,0);
         j=i+st;
         k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]){
               st++;
               j++;
               k++;
         }
         height[rank[i]]=st;
     }
}

另外再有一个定理lcp(i,j)=min(lcp(k-1,k)) (k∈(i,j])

姑且叫他lcp(i,j)定理

然后我们就可以用它解决很多问题。

总的来说有:

1、多串匹配。

复杂度O( (T+lgN)*M)   其中T为模式串长度,N为主串长度,M为模式串个数。

主要思想就是二分,然后利用height数组,和lcp(i,j)定理。

2、最长公共前缀。

例题:http://hi.baidu.com/edwardmj/blog/item/a69c46560990d5143a2935fb.html

就是max(height[i])

3、最长回文子串。

设给定S’,求其最长回文子串。(设其长度为n)

令S”为S’的倒序串(即S”[n-i+1]=S'[i])

然后S=S’+’#’+S”。(即把两串连接)(长度为2*n+1)

然后枚举中心i(1<=i<=n),其镜像中心为2*n+2-i

然后就是求最多能延伸多长。

即求lcp(i,i’)。利用lcp(i,j)定理加上Sparse Table(RMQ)就可以做到在O(1)的复杂度内解决延伸问题。

所以,求最长回文子串的部分,复杂度为O(N)

总复杂度O(nlgn)(加上构造时间)

4、利用分组思想做一些意想不到的操作.

例如:http://hi.baidu.com/edwardmj/blog/item/e5105b8d97842ef1513d92ed.html

POJ 2774 后缀数组——最长公共子串

题意:

给定a串和b串,求他们的最长公共子串

分析:

把两个串连在一起。构造后缀数组。然后在构造等同于lcp(i-1,i)的height数组。

然后如果相邻的两个后缀分别属于a串和b串,那么就可以做答案。

时间复杂度O(nlgn)

1A

PS:第一次写后缀数组,写得有点繁杂,写多了,就会缩短了。。。

code:

#include #include #include #include #define N 300000
using namespace std;
char s[N],s1[N],s2[N];
struct gtp{int x,data[3],next;}g[N];
int n,len1,len2,sa[N],rank[N],a[N][3],e,ls[N],height[N];

void init(){
     scanf("%s",&s1);
     scanf("%s",&s2);
     len1=strlen(s1);
     len2=strlen(s2);
     n=0;
     for (int i=0;i         n++;
         s[n]=s1[i];
     }
     for (int i=0;i         n++;
         s[n]=s2[i];
     }
     s[0]=7;
}

void Sort(int l,int r){
     if (l>=r) return;
     int i=l,j=r;
     char mid=s[sa[(l+r)/2]];
     do{
          while (s[sa[i]]          while (s[sa[j]]>mid) j–;
          if (i<=j){
            swap(sa[i],sa[j]);
            i++; j–;
          }
     }while (i     Sort(l,j);
     Sort(i,r);
}

inline void add(int x,int data[]){
       e++;
       g[e].x=x;
       memcpy(g[e].data,data,sizeof(a[0]));
       g[e].next=ls[x];
       ls[x]=e;
}

void Jsort(){
     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=1;i<=n;i++)
       add(a[i][1],a[i]);
     int tail=0;
     for (int i=0;i<=n;i++){
         for (int t=ls[i];t!=0;t=g[t].next){
             tail++;
             memcpy(a[tail],g[t].data,sizeof(a[0]));
         }
     }

     e=0;
     memset(ls,0,sizeof(int)*(n+2));
     for (int i=n;i>=1;i–)
       add(a[i][0],a[i]);
     tail=0;
     for (int i=0;i<=n;i++)
       for (int t=ls[i];t!=0;t=g[t].next){
           tail++;
           memcpy(a[tail],g[t].data,sizeof(a[0]));
       }
}

inline bool flag(int d1[],int d2[]){
       if (d1[0]!=d2[0] || d1[1]!=d2[1]) return true;
       return false;
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     Sort(1,n);
     int t=0;
     for (int i=1;i<=n;i++){
       if (t==0 || s[sa[i]]!=s[sa[i-1]]) t++;
       rank[sa[i]]=t;
     }
     for (int i=1;1<         for (int j=1;j<=n;j++){
             a[j][0]=rank[j];
             if (j+(1<                          else a[j][1]=rank[j+(1<             a[j][2]=j;
         }
         Jsort();
         int t=0;
         for (int j=1;j<=n;j++){
             if (t==0 || flag(a[j],a[j-1])) t++;
             rank[a[j][2]]=t;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void lcp(){
     memset(height,0,sizeof(height));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st,j,k;
         st=max(height[rank[i-1]]-1,0);
         j=i+st;
         k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]){
               st++;
               j++;
               k++;
         }
         height[rank[i]]=st;
     }
}

inline bool part(int k){
            if (k<=len1) return true;
            return false;
       }

void print(){
     int ans=0;
     for (int i=2;i<=n;i++)
       if (part(sa[i-1])^part(sa[i])) ans=max(ans,height[i]);
     cout << ans << endl;
}

int main(){
    init();
    buildarr();
    lcp();
    print();
}

POJ 2125 最小点权覆盖(最小割)

题意:

给出N个点和M条边

再给出ai和bi。

ai表示删除i的所有入边的权值

bi表示删除i的所有出边的权值

然后给出那些边。

求怎样用最小的代价,删除所有的边。

分析:

详细的可以看amber的最小割论文

http://u.115.com/file/f7142414ae

过期的话就百度一下吧。。。

具体名字是《最小割模型在信息学竞赛中的应用》

就是最小点权覆盖(用最少的点权覆盖所有的边)

我们把每个点拆成两个点。

对于每个bi,建边(S,i,bi)

对于每个ai,建边(i+n,T,ai)

然后每条图中的边,建边(i,j+n,INF)

然后求最大流,最后求最小割即可。

插曲:

一开始ai和bi弄反了。WA到SB了

code:

#include #include #define N 100000
#define E 2000000
#define INF 0x7FFFFFFF
using namespace std;
struct edge{int x,y,c,op,next;}g[E];
int n,e=0,ls[N],fa[N],cur[N],d[N],num[N],v[N],ans[N];

void add(int x,int y,int c){
       e++;
       g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
       e++;
       g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

void init(){
     memset(ls,0,sizeof(ls));
     memset(fa,0,sizeof(fa));
     memset(cur,0,sizeof(cur));
     memset(d,0,sizeof(d));
     memset(num,0,sizeof(num));
     memset(v,0,sizeof(v));
     int m,x,y;
     cin >> n >> m;
     for (int i=1;i<=n;i++){
         cin >> x;
         add(i+n,n+n+1,x);
     }
     for (int i=1;i<=n;i++){
         cin >> x;
         add(0,i,x);
     }
     for (int i=1;i<=m;i++){
         cin >> x >> y;
         add(x,y+n,INF);
     }
}

void relabel(int k){
     cur[k]=ls[k];
     int min=n+n+1;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (g[i].c>0 && d[g[i].y]     d[k]=min+1;
}

int change(){
    int nf=INF;
    for (int i=n+n+1;i!=0;i=g[fa[i]].x)
      nf=min(nf,g[fa[i]].c);
    for (int i=n+n+1;i!=0;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
    return nf;
}

int sap(){
    int flow=0;
    for (int i=0;i<=n+n+1;i++) cur[i]=ls[i];
    num[0]=n+n+2;
    int i=0;
    while (d[0]          for (;cur[i]!=0;cur[i]=g[cur[i]].next)
              if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
          if (cur[i]==0){
            if (–num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
          }
          else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+n+1){
              flow+=change();
              i=0;
            }
          }
    }
    return flow;
}

void dfs(int k){
     d[k]=1;
     v[k]=0;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (d[g[i].y]==0 && g[i].c>0) dfs(g[i].y);
}

void print(){
     int t=0;
     for (int i=0;i<=N;i++) v[i]=1;
     memset(d,0,sizeof(d));
     dfs(0);
     for (int i=1;i<=e;i=i+2)
       if (v[g[i].x]==0 && v[g[i].y]==1 && g[i].c==0)
         ans[t++]=i;
     cout << t << endl;
     for (int i=0;i       if (g[ans[i]].x==0) cout << g[ans[i]].y << " -" << endl;
                      else cout << g[ans[i]].x-n<<" +" << endl;
}

int main(){
    init();
    int flow=sap();
    cout << flow << endl;
    print();
}

POJ 2892 平衡树or线段树

题意:

给出直线上一系列的村庄,如果相邻村庄都没有被破坏,则两村庄是连接的,题目给出一系列的破坏操作,对指定号码的村庄进行破坏,还有一系列的询问操作,询问与指定号码的村庄直接相连或间接相连的村庄有几个,还有一个修复操作,是对最后破坏的村庄进行修复。

分析:

我们可以建立一棵平衡树,储存已经删除了的结点。

然后查询个数可以用平衡树找到比我大一点点的那个村庄和小一点点的那个村庄。

破坏的话就是插入了。

修复的话就是删除。

当然,线段树也可以实现这些操作。

插曲:

本来可以1A的。。。忘了删文件,又贡献WA一个。

第一次用类(对象)来写程序吖

code:

#include #include using namespace std;
const int N=1000000;
const int INF=0x7FFFFFFF;
int n,q,L[N],Lt=0,v[N];
class sbttype{
       public:
       int tot,root;
       struct treetype{int l,r,s,w;}tr[N];
       void Left(int &p){
            int t=tr[p].r;
            tr[p].r=tr[t].l;
            tr[t].l=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Right(int &p){
            int t=tr[p].l;
            tr[p].l=tr[t].r;
            tr[t].r=p;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
            p=t;
            tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
       }
       void Repair(int &p){
            bool flag=false;
            if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
              Left(tr[p].l);
              Right(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
              Left(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
              Right(tr[p].r);
              Left(p);
              flag=true;
            }
            if (flag){
              Repair(tr[p].l);
              Repair(tr[p].r);
              Repair(p);
            }
       }
       void ins(int &p,int w){
            if (p==0){
              tr[++tot].l=0;
              tr[tot].r=0;
              tr[tot].s=1;
              tr[tot].w=w;
              p=tot;
              return;
            }
            if (w                      else ins(tr[p].r,w);
            Repair(p);
       }
       int del(int &p,int w){
           if (tr[p].w==w || tr[p].l==0 && w             int delnum=tr[p].w;
             if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
                                      else tr[p].w=del(tr[p].l,INF);
             return delnum;
           }
           if (w                     else return del(tr[p].r,w);
       }
       int fewmin(int p,int w){
           if (p==0) return 0;
           if (w<=tr[p].w) return fewmin(tr[p].l,w);
           return max(tr[p].w,fewmin(tr[p].r,w));
       }
       int fewmax(int p,int w){
           if (p==0) return n+1;
           if (w>=tr[p].w) return fewmax(tr[p].r,w);
           return min(tr[p].w,fewmax(tr[p].l,w));
       }
}sbt;

int main(){
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     scanf("%d%dn",&n,&q);
     sbt.root=0;
     sbt.tot=0;
     char ch;
     int x;
     for (int i=1;i<=q;i++){
         scanf("%c",&ch);
         if (ch==’R’){
           while (Lt>0 && v[L[Lt]]==0) Lt–;
           if (Lt>0){
             sbt.del(sbt.root,L[Lt]);
             v[L[Lt]]=0;
             Lt–;
           }
           scanf("n");
         }
         else if (ch==’Q’){
              scanf("%dn",&x);
              if (v[x]==1) {printf("0n");continue;}
              int tl=sbt.fewmin(sbt.root,x),tr=sbt.fewmax(sbt.root,x);
              printf("%dn",tr-tl-1);
         }
         else{
              scanf("%dn",&x);
              if (v[x]==1) continue;
              v[x]=1;
              sbt.ins(sbt.root,x);
              L[++Lt]=x;
         }
     }
    return 0;
}

SGU 148 堆优化+模拟 or 平衡树

题意:

有一个大水桶,里面有N层。从上至下标为1、2、3…层。

如果破坏某一层(需要一定代价),那么水就会流到下一层。

另外,如果某一层的水量超过了他能负荷的水量。也会自动爆炸。。。水就会自动流到下一层。

现在你是恐怖分子,求怎样花费最少,可以破坏掉第N层。

分析:

首先水不可能是断流的。因为这样上面一层就没有任何意义了。

所以我们可以枚举水开始下流在哪一层。如果中间遇到水量不够自动破坏,就需要破坏掉这一层(即付出相应花费)。

这样到达每一个层的水量就是sum(i,j)其中i为开始流的层,j表示当前层。

我们发现这满足单调性。我们把i从N枚举到1。再用堆or平衡树维护即可。

因为i减1不会破坏他们的大小关系。

code:

#include #include using namespace std;
const int N=20000;
const int INF=0x7FFFFFFF;
struct headtype{int limit,w,p,i;} heap[100000];
int n,tot=0,water[N],limit[N],p[N],Swater=0,outtime[N];

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++)
       scanf("%d%d%d",&water[i],&limit[i],&p[i]);
}

inline int f(int t){
       return (heap[t].limit-heap[t].w);
}

void up(int k){
     while (k>1 && f(k/2)>f(k)){
           swap(heap[k],heap[k/2]);
           k/=2;
     }
}

void down(int k){
     while (k*2<=tot){
           int t;
           if (k*2+1<=tot && f(k*2+1)                                         else t=k*2;
           if (f(t)           k=t;
     }
}

void ins(int W,int L,int P,int i){
     tot++;
     heap[tot].w=W;
     heap[tot].limit=L;
     heap[tot].p=P;
     heap[tot].i=i;
     up(tot);
}

void del(){
     heap[1]=heap[tot];
     tot–;
     down(1);
}

void work(){
     int ans=INF,now=0,ansi=0;
     for (int i=n;i>=1;i–){
         Swater+=water[i];
         now+=p[i];
         ins(water[i]-Swater,limit[i],p[i],i);
         while (tot>0 && heap[1].w+Swater>heap[1].limit){
               now-=heap[1].p;
               outtime[heap[1].i]=i;
               del();
         }
         if (now           ans=now;
           ansi=i;
         }
     }
     for (int i=ansi;i<=n;i++)
       if (outtime[i]}

int main(){
    init();
    work();
}