程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 3415 SAM後綴自動機

poj 3415 SAM後綴自動機

編輯:關於C++
題意:

給出兩個串,問這兩個串的所有的子串中(重復出現的,只要是位置不同就算兩個子串),長度大於等於k的公共子串有多少個。

 

設A串構造SAM,B串去匹配A串

狀態再添加一個值:sum,指這個狀態出現多少次了。也就是說B串裡面有多少個子串可以進入這個狀態。

逆拓撲排序更新父親結點。

 

匹配過程中:

注意一點,匹配過程中進入某個狀態的串的長度是不固定的。

每次匹配長度lcs>=n時,當前狀態符合條件的子串的數量為:(lcs-max(n,p->f->len+1)+1),這個數量是不固定的。這個狀態出現的次數為 p->right 。

如果p->f->len>=n,父親狀態是有符合狀態的子串,而且符合狀態的子串的數量是固定的。

先把這部分不固定的子串數量在匹配的過程中直接處理了。ans+=(lcs-max(n,p->f->len+1)+1)*p->right; 此時父親狀態出現的次數加一,p->f->sum++;

對於父親狀態,由於符合狀態的子串的數量是固定的,所以可以先把這個狀態出現的次數先求出來,等待匹配結束後再處理。

 

逆拓撲排序更新父親結點的出現次數

對於每個結點>=n的狀態

ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);

//出現次數*right集合大小*符合條件的子串數量

 

 


//len表示該狀態可以接受的最長的字符串長度,即max,
//那麼該狀態可以接受的最短的字符串長度為p->f->len+1
//子串儲存在狀態裡當且僅當字符串S,ST(S)!=NULL,S才為子串
//SAM 中的每個狀態能夠表示的不同子串的個數為 val - 父結點的 val
//所以在每增加一個點,或者說每次新建一個子父關系的時候,累加該狀態所產生的子串數量
//求子串出現的數量等於求所在狀態的right的集合大小,暫時還不會
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn=100100;
struct suffixautomaton
{
    struct node
    {
        long long len;//到這個狀態允許的最大長長度,即max(s)
        long long right;//這個狀態在這個串裡有幾個位置,即right集合的大小
        long long sum;
        node *f,*ch[60];  //
        node(){}
        node(int l)
        {
            len=l;
            f=NULL;
            right=0;
            sum=0;
            memset(ch,0,sizeof(ch));
        }
        int calc()   //返回該狀態包含的子串數量
        {
            if(f==NULL)return 0;//
            return len-(f->len);
        }
    };
    node *root,*last;
    node pool[maxn*2];  //儲蓄結點用的
    int cnt;             //結點的數量
    int tot;   //當前sam可以表示的不同子串的數量,當建立子-父結點是,計算一次可以表示多少個子串
                //當更改子-父關系時,必須先減去之前的狀態所表示子串數量
    void init()
    {
        root=last=pool;
        memset(root,0,sizeof(node));
        cnt=1;
        tot=0;
    }
    node * new_node(int l=0)
    {
        node *x=pool+cnt++;
        memset(x,0,sizeof(node));
        if(l!=0) x->len=l;
        return x;
    }
    void add(char ch)
    {
        int c=ch-'A';
        node *p=last,*np=new_node(last->len+1);
        while(p&&!p->ch[c])
            p->ch[c]=np,p=p->f;
        if(NULL==p)
        {
            np->f=root;  //建立子父關系
            tot+=np->calc();  //計算增加的子串。下同
        }
        else
        {
            if(p->ch[c]->len==p->len+1)
            {
                np->f=p->ch[c];
                tot+=np->calc();
            }
            else
            {
                node *q=p->ch[c],*nq=new_node();
                *nq=*q;           //nq也建立了子父關系,nq->f=q->f;
                nq->len=p->len+1;  //新建立nq
                tot-=q->calc();     //q點要更換子父關系,先減去
                q->f=np->f=nq;
                tot+=q->calc()+nq->calc()+np->calc(); //此處新建三個子父關系
                while(p&&p->ch[c]==q)
                    p->ch[c]=nq,p=p->f;
            }
        }
        last=np;
}

    int bus[maxn*2];    //處理
    int sorted[maxn*2];  //0--(cnt-1)為拓撲排序的出序順序

    void findr(char str[])  //處理某狀態的right集合的大小,如果想要找到位置,node必須有東西標志位置
    {
        int l=strlen(str);
        memset(bus,0,sizeof(bus));
        for(int i=0;ich[str[i]-'A'])->right++;
        for(int i=cnt-1;i>0;i--)
            if(pool[sorted[i]].f)
                pool[sorted[i]].f->right+=pool[sorted[i]].right;
        root->right=0;  //還原
    }
    void solve()  //求sum
    {
        node *p=root;
        for(int i=cnt-1;i>0;i--)
            if(pool[sorted[i]].f)
                pool[sorted[i]].f->sum+=pool[sorted[i]].sum;
        root->sum=0;
    }
};
suffixautomaton sam;
char str[maxn];
char str2[maxn];
int main()
{
    long long n;
    while(scanf("%lld",&n),n)
    {
        scanf("%s",str);
        sam.init();
        int len=strlen(str);
        for(int i=0;ich[c])
                p=p->ch[c],lcs++;
            else
            {
                while(p&&!p->ch[c])  p=p->f;
                if(p==NULL)  p=sam.root,lcs=0;
                else lcs=p->len+1,p=p->ch[c];
            }
            if(lcs>=n)
            {
                ans+=(lcs-max(n,p->f->len+1)+1)*p->right;  //由於其的不固定性。直接處理了
                p->f->sum++;//父親出現次數加一
            }
        }
        sam.solve();
        for(int i=0;i=n)  //對於符合的點,
                ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
























 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved