首先，我們來定義一下淋漓盡致子串。 1.令原串為S。 2.設(shè)子串的長度為len，在原串S中出現(xiàn)的次數(shù)為k，令其出現(xiàn)的位置為p1， p2， ....pk(即這個子串在原串中[pi，pi + len - 1]中出現(xiàn))。
3.若k=1，則該子串不是淋漓盡致子串。 4.若存在pi，pj(i != j)，使得S[pi - 1] = S[pj - 1]，則該子串不是淋漓盡致子串。 5.若存在pi，pj(i != j)，使得S[pi + len] = S[pj + len]，則該字串不是淋漓盡致字串。 否則，該子串為淋漓盡致子串。 我想知道這個串有多少個本質(zhì)不同的淋漓盡致子串。 數(shù)據(jù)范圍： |S| <= 100000 S由小寫字母組成。 考慮用SAM，來分析一下題目中的條件 首先出現(xiàn)超過一次，即sz[i]>1 條件4，即滿足在parent樹上，沒有一個i的兒子j滿足sz[j]>1 條件5，滿足在轉(zhuǎn)移DAG上，沒有一個兒子j滿足sz[j]>1 于是每找到一個節(jié)點，就會為答案貢獻1 #pragma GCC opitmize("O3") #pragma G++ opitmize("O3") #include<stdio.h> #include<string.h> #include<algorithm> #define N 200010 using namespace std; char str[N]; int ans=0; int s[N][26],mx[N],sz[N],f[N]; int n,m,cnt=1,lst=1,v[N],r[N]; inline int extend(int c){int p=lst,np=lst=++cnt,q,nq;mx[np]=mx[p]+1; sz[np]=1;for(;!s[p][c];p=f[p]) s[p][c]=np;if(!p) return f[np]=1;q=s[p][c];if(mx[q]==mx[p]+1) f[np]=q;else{nq=++cnt;mx[nq]=mx[p]+1;f[nq]=f[q]; f[q]=f[np]=nq;memcpy(s[nq],s[q],26<<2);for(;p&&s[p][c]==q;p=f[p]) s[p][c]=nq;} } int main(){scanf("%s",str+1); n=strlen(str+1);for(int i=1;i<=n;++i) extend(str[i]-'a');for(int i=1;i<=cnt;++i) ++v[mx[i]];for(int i=1;i<=n;++i) v[i]+=v[i-1];for(int i=cnt;i;--i) r[v[mx[i]]--]=i;for(int i=cnt;i;--i) sz[f[r[i]]]+=sz[r[i]];memset(v,*sz=0,sizeof v);for(int p,i=cnt;i;--i){p=r[i];if(sz[p]>1) v[f[p]]=1;if(sz[p]==1) v[p]=1; else for(int c=0;c<26;++c)if(sz[s[p][c]]>1){ v[p]=1; break; }}for(int i=cnt;i;--i) ans+=!v[i];printf("%d\n",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/Extended-Ash/p/9477134.html

總結(jié)

以上是生活随笔為你收集整理的51Nod1469 淋漓尽致子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。