ACdream 1430 SETI 后缀自动机/后缀数组 不重叠子串的个数

时间：2022-09-03 12:06:42

题目求不重叠子串的个数。

一开始看错题第一反应就是用SAM来解，求出right集，如果出现次数超过1次就统计。

不过本题要求的是不重叠的子串，因此在求right集时，顺便维护两个值，每个结点所能表示的所有原串的终点的最小值和最大值。

最后遍历所有结点统计答案。O(n)

如果用SA来做的话就是枚举所有的子串长度k，对于每个k，对heght进行分组，对每个分组，求出sa最小值和最大值，最大值减去最小值是否不小于k，如果是就把答案加一。

枚举O(n)，统计O(n)，总复杂度O(n^2)，由于时限是10s所以没超时。


/*
* this code is made by cyendra
* Problem: 1430
* Verdict: Accepted
* Submission Date: 2014-10-06 18:07:26
* Time: 96MS
* Memory: 14864KB
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=30000;
const int maxm=13000;
/***************
    SAM 真·模板
***************/
struct State {
    State *par;
    State *go[52];
    int val; // max，当前状态能接收的串的最长长度
    int mi;
    int mx;
    int right; // right集，表示当前状态可以在多少个位置上出现
    void init(int _val = 0){
        par = 0;
        val = _val;
        mx=-1;
        mi=INF;
        right=0;
        memset(go,0,sizeof(go));
    }
    int calc(){ // 表示该状态能表示多少中不同的串
        if (par==0) return 0;
        return val-par->val;
    }
};
State *root, *last, *cur;
State nodePool[maxn];
State* newState(int val = 0) {
    cur->init(val);
    return cur++;
}
//int total; // 不同的子串个数。
void initSAM() {
    //total = 0;
    cur = nodePool;
    root = newState();
    last = root;
}
void extend(int w,int pos) {
    State* p = last;
    State* np = newState(p->val + 1);
    np->right=1; // 设置right集
    np->mi=np->mx=pos;
    while (p && p->go[w] == 0) {
        p->go[w] = np;
        p = p->par;
    }
    if (p == 0) {
        np->par = root;
        //total+=np->calc();
    }
    else {
        State* q = p->go[w];
        if (p->val + 1 == q->val) {
            np->par = q;
            //total+=np->calc();
        }
        else {
            State* nq = newState(p->val + 1);
            memcpy(nq->go, q->go, sizeof(q->go));
            //total -= q->calc();
            nq->par = q->par;
            q->par = nq;
            np->par = nq;
            //total += q->calc()+nq->calc()+np->calc();
            while (p && p->go[w] == q) {
                p->go[w] = nq;
                p = p->par;
            }
        }
    }
    last = np;
}

int d[maxm];
State* b[maxn];
void topo(){ // 求出parent树的拓扑序
    int cnt=cur-nodePool;
    int maxVal=0;
    memset(d,0,sizeof(d));
    for (int i=1;i<cnt;i++) maxVal=max(maxVal,nodePool[i].val),d[nodePool[i].val]++;
    for (int i=1;i<=maxVal;i++) d[i]+=d[i-1];
    for (int i=1;i<cnt;i++) b[d[nodePool[i].val]--]=&nodePool[i];
    b[0]=root;
}

void gaoSamInit(){ // 求出SAM的附加信息
    State* p;
    int cnt=cur-nodePool;
    for (int i=cnt-1;i>0;i--){
        p=b[i];
        p->par->right+=p->right;
        p->par->mi=min(p->par->mi,p->mi);
        p->par->mx=max(p->par->mx,p->mx);
    }
}


char s[maxm];

int main()
{
    scanf("%s",s);
    initSAM();
    for (int i=0;s[i];i++){
        extend(s[i]-'a',i);
    }
    topo();
    gaoSamInit();
    int ans=0;
    State* p;
    int cnt=cur-nodePool;
    for (int i=cnt-1;i>0;i--){
        p=b[i];
        if (p->right>1) {
            int lim=p->mx-p->mi;
            int L=p->par->val+1;
            int R=p->val;
            if (R<=lim) ans+=p->calc();
            else if (L>lim) continue;
            else if (lim>=L&&lim<R) ans+=lim-L+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}


--------

/*
* this code is made by cyendra
* Problem: 1430
* Verdict: Accepted
* Submission Date: 2014-10-06 13:10:01
* Time: 5740MS
* Memory: 3804KB
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long LL;
const int maxn=20000;
const int maxm=13000;
const int INF=0x3f3f3f3f;
/******************************************************************
**  后缀数组 Suffix Array
**  INIT：solver.call_fun(char* s);
**  CALL: solver.lcp(int i,int j); //后缀i与后缀j的最长公共前缀
**  SP_USE: solver.LCS(char *s1,char* s2); //最长公共字串
******************************************************************/
struct SuffixArray{
    int r[maxn];
    int sa[maxn],rank[maxn],height[maxn];
    int t[maxn],t2[maxn],c[maxn],n;
    int m;//模板长度
    void init(char* s){
        n=strlen(s);
        for (int i=0;i<n;i++) r[i]=int(s[i]);
        m=300;
    }
    int cmp(int *r,int a,int b,int l){
        return r[a]==r[b]&&r[a+l]==r[b+l];
    }
    /**
    字符要先转化为正整数
    待排序的字符串放在r[]数组中，从r[0]到r[n-1]，长度为n，且最大值小于m。
    所有的r[i]都大于0,r[n]无意义算法中置0
    函数结束后，结果放在sa[]数组中(名次从1..n)，从sa[1]到sa[n]。s[0]无意义
    **/
    void build_sa(){
        int i,k,p,*x=t,*y=t2;
        r[n++]=0;
        for (i=0;i<m;i++) c[i]=0;
        for (i=0;i<n;i++) c[x[i]=r[i]]++;
        for (i=1;i<m;i++) c[i]+=c[i-1];
        for (i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
        for (k=1,p=1;k<n;k*=2,m=p){
            for (p=0,i=n-k;i<n;i++) y[p++]=i;
            for (i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k;
            for (i=0;i<m;i++) c[i]=0;
            for (i=0;i<n;i++) c[x[y[i]]]++;
            for (i=1;i<m;i++) c[i]+=c[i-1];
            for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;
            x[sa[0]]=0;
            for (i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
        }
        n--;
    }
    /**
    height[2..n]:height[i]保存的是lcp(sa[i],sa[i-1])
    rank[0..n-1]:rank[i]保存的是原串中suffix[i]的名次
    **/
    void getHeight(){
        int i,j,k=0;
        for (i=1;i<=n;i++) rank[sa[i]]=i;
        for (i=0;i<n;i++){
            if (k) k--;
            j=sa[rank[i]-1];
            while (r[i+k]==r[j+k]) k++;
            height[rank[i]]=k;
        }
    }
    int d[maxn][20];
    //元素从1编号到n
    void RMQ_init(int A[],int n){
        for (int i=1;i<=n;i++) d[i][0]=A[i];
        for (int j=1;(1<<j)<=n;j++)
            for (int i=1;i+j-1<=n;i++)
                d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    }
    int RMQ(int L,int R){
        int k=0;
        while ((1<<(k+1))<=R-L+1) k++;
        return min(d[L][k],d[R-(1<<k)+1][k]);
    }
    void LCP_init(){
        RMQ_init(height,n);
    }
    int lcp(int i,int j){
        if (rank[i]>rank[j]) swap(i,j);
        return RMQ(rank[i]+1,rank[j]);
    }
    void call_fun(char* s){
        init(s);//初始化后缀数组
        build_sa();//构造后缀数组sa
        getHeight();//计算height与rank
        LCP_init();//初始化RMQ
    }
    int LCS(char* s1,char* s2){
        int p,ans;
        int l=strlen(s1);
        p=l;
        s1[l]='$';
        s1[l+1]='\0';
        strcat(s1,s2);
        call_fun(s1);
        ans=0;
        for (int i=2;i<=n;i++)
            if ((sa[i-1]<p&&sa[i]>p)||(sa[i-1]>p&&sa[i]<p)) ans=max(ans,height[i]);
        return ans;
    }
    int gao(int k,int n){
        int maxx=0,minn=INF,ans=0;
        for (int i=2;i<=n;i++){
            if (height[i]<k){
                if (maxx-minn>=k){
                    ans++;
                }
                maxx=0,minn=INF;
            }
            else{
                maxx=max(maxx,max(sa[i-1],sa[i]));
                minn=min(minn,min(sa[i-1],sa[i]));
            }
        }
        if (maxx-minn>=k) ans++;
        return ans;
    }
}solver;

char s[maxn];
int main()
{
    //freopen("seti.in","r",stdin);
    //freopen("seti.out","w",stdout);
    scanf("%s",s);
    //gets(s);
    int len=strlen(s);
    solver.init(s);
    solver.build_sa();
    solver.getHeight();
    int ans=0;
    for (int i=1;i<=len/2;i++){
        ans+=solver.gao(i,len);
    }
    printf("%d\n",ans);
    return 0;
}




标签：

相关文章