給出兩個串,問這兩個串的所有的子串中(重復出現的,只要是位置不同就算兩個子串),長度大於等於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;i ch[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;i ch[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; }