算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    给N个串(N<100,000),总长不超过100,000。对于每个串,求至少在其他k个串中作为子串出现过的子串个数。

算法分析:

    
    不难想到在若干个串中,找满足****性质的子串,可以用后缀数组求LCP解决。
    这里有一个性质,就是如果对于串S的后缀串Si,子串Sij满足题目的性质,那么Sii...Sij都会满足。
    这样解的分部具有单调性,二分答案来求解。
    对于串LCPij,我们要找到含有LCPij的所有后缀串。用线段树不难找到。
    设LCP(p...q)都含有Sij。下面我们的问题是,LCP(p...q)对应多少个原串。
    一开始我也蒙了,后来才知道根本不用求出对应多少个原串,只需知道是否大于等于k就可以了。
    我们扫一遍,预处理出LCP数组中对于r,最大的满足LCP(l,r)对应k个原串的l。
    这题非常爽!! 又AK了一场,更爽!!!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cassert>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int BS = 37;
const int N = 2* int(1e5) + 10;
char ch[N];
ull hash[N], base[N], ans[N];
int sa[N], lcp[N], pos[N] , n , k, P[N];
int seg[N<<2], M, len;
// suffix array
inline int cal(int a,int b,int c){
    if( a > b) swap(a,b);
    int l = 0;
    int r; if(c==0) r = len-b;
    else r = min(pos[P[a]+1]-a-1,pos[P[b]+1]-b-1);
    while(l<r){
        int mid = l+r >>1;
        if( hash[a] - hash[a + mid + 1] == (hash[b] - hash[b + mid + 1]) * base[b-a]) l = mid + 1; else r = mid;
    }
    return r;
}
bool cmp(int a,int b) {
    int l = cal(a,b,0);
    if(a + l == len) return 1;
    if(b + l == len) return 0;
    assert(ch[a+l] != ch[b+l]);
    return ch[a+l] < ch[b+l];
}
// queue
int flag[N],R[N],pa[N];
void init(){
    for(int i=0;i<len;i++){
        pa[i] = P[sa[i]];
        flag[i] = -1;
    }
    int cnt = 0,now = 0;
    for(int i=0;i<len;i++){
        if(flag[pa[i]] == -1){
            cnt ++;
        }
        flag[pa[i]] = i;
        if(cnt<k) R[i] = now;
        else if(cnt == k){
            while(flag[pa[now]]!= now) now++;
            R[i] = now;
        }
        else {
            flag[pa[now]] = -1;
            now ++;
            while(flag[pa[now]]!= now) now++;
            R[i] = now;
            cnt --;
        }
    }
}
// segment tree
int dfs(int p,int c,int v){
    if(p >= M) return p;
    if(c){
        if(seg[p<<1|1] < v)return dfs(p<<1|1,c,v);
        else return dfs(p<<1,c,v);
    }
    else {
        if(seg[p<<1] < v) return dfs(p<<1,c,v);
        else return dfs(p<<1|1,c,v);
    }
}
bool upt(int p,int v){
    if(v == 0) return N;
//    cout<<"upt: "<<p<<" "<<v<<" ";
    int r = -1, l = -1;
    if(seg[p+=M] < v) r = p;
    for(;p>1;p>>=1){
        if(p&1) if(l==-1) if(seg[p^1] < v) l = dfs(p^1,1,v);
        if(~p&1) if(r==-1) if(seg[p^1]< v) r = dfs(p^1,0,v);
    }
//    cout<<l-M<<" "<<r-M<<endl;
    l-=M, r-=M;
    return R[r] > l;
}
// debug
int OP(int p){while(ch[p]!='$') cout<<ch[p++];}
// main
int main(){
    base[0] = 1;
    for(int i=1;i<N;i++) base[i] = base[i-1] * BS;
    while(~scanf("%d%d",&n,&k)){
        pos[0] = 0;
        for(int i=0;i<n;i++){
            scanf("%s",ch + pos[i]);
            pos[i+1] = pos[i] + strlen(ch + pos[i]) + 1;
            ch[pos[i+1]-1] = '$';
        }
        len = pos[n];
        int nowp = 0;
        for(int i=0;i<len;i++) {P[i] = nowp; if(ch[i]=='$') nowp++;}
//        for(int i=0;i<len;i++) cout<<P[i]<<" "; cout<<endl;
        
// build lcp
        hash[len]  = 0;
        for(int i=len-1;i>=0; i--)
            hash[i] = hash[i+1]+ base[len-1-i] * (ch[i] == '$' ? 0 : ch[i] - 'a' + 1);
        for(int i=0;i<len;i++) sa[i] = i;
        stable_sort(sa, sa + len, cmp);
        for(int i=0;i<len-1;i++) lcp[i] = cal(sa[i],sa[i+1],1);
        lcp[len] = lcp[len-1] = 0;
        // build seg
        for(int i=30;i;i--) if((1<<i) > len) M = 1<<i;
        for(int i=M;i<M+M;i++) seg[i] = ~0u>>2;
        for(int i=0;i<=len;i++) seg[i+M] = lcp[i];
        for(int i=M-1;i;i--) seg[i] = min(seg[i<<1] , seg[i<<1|1]);
        init();
        memset(ans,0,sizeof(ans));
        for(int i = n; i < len; i++){
            int p = P[sa[i]];
            int l = 0, r = pos[p+1] - sa[i] ;
//            OP(sa[i]); cout<<" "<<l<<" "<<r<<endl;
            while(l<r) {
                int mid = l + r >> 1; 
                if( upt(i,mid)) l = mid +1;
                else r = mid;
            }
//            OP(sa[i]);cout<<" "<<lcp[i]<<" "<<r-1<<endl;
            ans[p] += r-1;
        }
        for(int i=0;i<n;i++)
            cout<<ans[i]<<" "; cout<<endl;
    }
}
posted on 2012-07-26 10:20 西月弦 阅读(732) 评论(1)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: codeforces 204E 后缀数组+线段树
2013-04-10 23:51 | acm爱好者
你好,不知可否此题在详述一下?我想此题想了很久了。。一直没懂怎么写,能否发邮件交流?luyuncheng@sina.com  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理