FZU-2075 Substring（后缀数组）

时间：2024-10-29 16:04:20

Description

Given a string, find a substring of it which the original string contains exactly n such substrings.

Input

There are several cases. The first line of each case contains an integer n.The second line contains a string, no longer than 100000.

Output

If the such substring doesn't exist, output "impossible", else output the substring that appeared n times in the original string.If there are multiple solutions, output lexicographic smallest substring.

Sample Input

2

ababba

Sample Output

ab

题目大意：给一个字符串，找出其恰好出现n次的字典序最小的子串。
题目分析：将所有的子串排序后，定义n块为相邻的n个子串构成的字符串集合，如果某个n块的lca大于包含它的n+1块的lca，那么这个n块的lca便是恰好出现了n次的子串。

代码如下：
//# define AC

# ifndef AC

# include<iostream>

# include<cstdio>

# include<cstring>

# include<vector>

# include<queue>

# include<list>

# include<cmath>

# include<set>

# include<map>

# include<string>

# include<cstdlib>

# include<algorithm>

using namespace std;

const int N=100000;

int SA[N+5];

int tSA[N+5];

int rk[N+5];

int cnt[N+5];

int height[N+5];

int *x,*y;

bool same(int i,int j,int k,int n)

{

    if(y[i]!=y[j]) return false;

    if(i+k<n&&j+k>=n) return false;

    if(i+k>=n&&j+k<n) return false;

    return y[i+k]==y[j+k];

}

void buildSA(char* s)

{

    x=rk,y=tSA;

    int m=130;

    int n=strlen(s);

    for(int i=0;i<m;++i) cnt[i]=0;

    for(int i=0;i<n;++i) ++cnt[x[i]=s[i]];

    for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];

    for(int i=n-1;i>=0;--i) SA[--cnt[x[i]]]=i;

    for(int k=1;k<=n;k<<=1){

        int p=0;

        for(int i=n-k;i<n;++i) y[p++]=i;

        for(int i=0;i<n;++i) if(SA[i]>=k) y[p++]=SA[i]-k;

        for(int i=0;i<m;++i) cnt[i]=0;

        for(int i=0;i<n;++i) ++cnt[x[y[i]]];

        for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];

        for(int i=n-1;i>=0;--i) SA[--cnt[x[y[i]]]]=y[i];

        p=1;

        swap(x,y);

        x[SA[0]]=0;

        for(int i=1;i<n;++i)

            x[SA[i]]=same(SA[i],SA[i-1],k,n)?p-1:p++;

        if(p>=n) break;

        m=p;

    }

}

void getHeight(char* s)

{

    int n=strlen(s);

    int k=0;

    for(int i=0;i<n;++i) rk[SA[i]]=i;

    for(int i=0;i<n;++i){

        if(rk[i]==0)

            height[rk[i]]=k=0;

        else{

            if(k) --k;

            int j=SA[rk[i]-1];

            while(s[i+k]==s[j+k]) ++k;

            height[rk[i]]=k;

        }

    }

}

char s[N+5];

int st[N+5][20];

void spare_table()

{

    int n=strlen(s);

    for(int i=1;i<n;++i)

        st[i][0]=height[i];

    for(int k=1;(1<<k)<=n;++k){

        for(int i=1;i+(1<<k)-1<n;++i){

            st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);

        }

    }

}

int getST(int l,int r)

{

    int k=0;

    while((1<<(k+1))<=r-l+1) ++k;

    return min(st[l][k],st[r-(1<<k)+1][k]);

}

string solve(int m)

{

    string res="";

    int n=strlen(s);

    int a,b,c;

    for(int i=0;i+m-1<n;++i){

        a=b=c=0;

        if(m==1) a=n-SA[i];

        else a=getST(i+1,i+m-1);

        if(i+m<n) b=getST(i+1,i+m);

        if(i>0) c=getST(i,i+m-1);

        if(a>b&&a>c){

            for(int j=SA[i];j<SA[i]+a;++j) res+=s[j];

            return res;

        }

    }

    return "impossible";

}

int main()

{

    int m;

    while(~scanf("%d",&m))

    {

        scanf("%s",s);

        buildSA(s);

        getHeight(s);

        spare_table();

        cout<<solve(m)<<endl;

    }

    return 0;

}

# endif

　　

相关文章