博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
后缀自动机小专题
阅读量：4993 次
发布时间：2019-06-12

本文共 21307 字，大约阅读时间需要 71 分钟。

菜鸡万年更博。

全是菜题。

 

SP1811 LCS - Longest Common Substring

对一个串建立自动机，另一个串在自动机上遍历，失配时跳father更新即可。ans=遍历到的点的len的最大值。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=25e4+3;char S[N],T[N];struct SAM{ int ch[26],fa,len;}sam[N<<1];int tot=1,lst=1;void insert(int x){ int p=lst;lst=++tot;sam[lst].len=sam[p].len+1; for(;p&&!sam[p].ch[x];p=sam[p].fa) sam[p].ch[x]=lst; if(!p) sam[lst].fa=1; else { int q=sam[p].ch[x]; if(sam[p].len+1==sam[q].len) sam[lst].fa=q; else { int nq=++tot;sam[nq]=sam[q],sam[nq].len=sam[p].len+1; sam[lst].fa=sam[q].fa=nq; for(;sam[p].ch[x]==q;p=sam[p].fa) sam[p].ch[x]=nq; } }}int main(){ scanf("%s%s",S+1,T+1); for(int i=1;S[i];++i) insert(S[i]-'a'); int now=1,len=0,Ans=0; for(int i=1;T[i];++i) { T[i]-='a'; if(sam[now].ch[T[i]]) ++len,now=sam[now].ch[T[i]]; else { while(now&&!sam[now].ch[T[i]]) now=sam[now].fa; if(!now) now=1,len=0; else len=sam[now].len+1,now=sam[now].ch[T[i]]; } Ans=max(Ans,len); } cout<
View Code

 

SP1812 LCS2 - Longest Common Substring II

可以跟上题一样做，也可以建个广义后缀自动机。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e5+5;int T,n;char s[N>>1];int ch[N][26],len[N],fa[N];int tot=1,lst=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;len[nq]=len[p]+1;fa[nq]=fa[q]; memmove(ch[nq],ch[q],sizeof(ch[q])); fa[q]=fa[lst]=nq; for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int cnt[N],sa[N];int mx[N],mn[N];int main(){ scanf("%s",s+1);int sl=strlen(s+1); lst=tot=1; for(int i=1;i<=sl;++i) insert(s[i]-'a'); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=sl;++i) cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;++i) sa[cnt[len[i]]--]=i; memset(mn,0x3f,sizeof(mn)); while(~scanf("%s",s+1)) { int now=1,L=0,x; for(int i=1;s[i];++i) { x=s[i]-'a'; while(now&&!ch[now][x]) now=fa[now],L=len[now]; if(!now) now=1,L=0; else ++L,now=ch[now][x],mx[now]=max(mx[now],L); } for(int i=tot,u,f;i;--i) { u=sa[i],f=fa[u]; mx[f]=max(mx[f],min(mx[u],len[f])); mn[u]=min(mn[u],mx[u]);mx[u]=0; } } int Ans=0; for(int i=1;i<=tot;++i) Ans=max(Ans,mn[i]); cout<
                 
                  <<'\n'; return 0;}
View Code 
#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_bound#include
                 
                  using namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e6+5;int id=-1;char s[100003];struct SAM{ int ch[26],fa,len; bitset<10> bst;}sam[N];int lst,tot=1;int newnode(int p,int q,int x){ int nq=++tot;sam[nq]=sam[q];sam[nq].len=sam[p].len+1; sam[q].fa=nq; for(;p&&sam[p].ch[x]==q;p=sam[p].fa) sam[p].ch[x]=nq; return nq;}int insert(int p,int x){ if(sam[p].ch[x]) { int q=sam[p].ch[x]; if(sam[p].len+1==sam[q].len) { sam[q].bst[id]=1; return q; } else { int nq=newnode(p,q,x); sam[nq].bst[id]=1; return nq; } } else { int np=++tot;sam[np].len=sam[p].len+1;sam[np].bst[id]=1; for(;p&&!sam[p].ch[x];p=sam[p].fa) sam[p].ch[x]=np; if(!p) sam[np].fa=1; else { int q=sam[p].ch[x]; if(sam[p].len+1==sam[q].len) sam[np].fa=q; else sam[np].fa=newnode(p,q,x); } return np; }}void debug(){ for(int i=1;i<=tot;++i) { for(int j=0;j<10;++j) cout<
                  
                   <<' '; puts(""); }}int cnt[N],sa[N];int main(){ while(~scanf("%s",s+1)) { lst=1;++id; for(int i=1;s[i];++i) lst=insert(lst,s[i]-'a'); } for(int i=1;i<=tot;++i) ++cnt[sam[i].len]; for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[sam[i].len]--]=i; int Ans=0;++id; for(int i=tot;i>1;--i) { if(sam[sa[i]].bst.count()==(unsigned)id) Ans=max(Ans,sam[sa[i]].len); sam[sam[sa[i]].fa].bst|=sam[sa[i]].bst; } cout<
广义后缀自动机

 

SP10570 LONGCS - Longest Common Substring

三倍经验

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e4+5;int T,n;char s[N>>1];int ch[N][26],len[N],fa[N];int tot=1,lst=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;len[nq]=len[p]+1;fa[nq]=fa[q]; memmove(ch[nq],ch[q],sizeof(ch[q])); fa[q]=fa[lst]=nq; for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int cnt[N],sa[N];int mx[N],mn[N];int main(){ T=read(); while(T--) { n=read();scanf("%s",s+1);int sl=strlen(s+1); lst=tot=1; memset(ch,0,sizeof(ch)); for(int i=1;i<=sl;++i) insert(s[i]-'a'); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=sl;++i) cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;++i) sa[cnt[len[i]]--]=i; memset(mn,0x3f,sizeof(mn)); for(int a=2;a<=n;++a) { scanf("%s",s+1); int now=1,L=0,x; for(int i=1;s[i];++i) { x=s[i]-'a'; while(now&&!ch[now][x]) now=fa[now],L=len[now]; if(!now) now=1,L=0; else ++L,now=ch[now][x],mx[now]=max(mx[now],L); } for(int i=tot,u,f;i;--i) { u=sa[i],f=fa[u]; mx[f]=max(mx[f],min(mx[u],len[f])); mn[u]=min(mn[u],mx[u]);mx[u]=0; } } int Ans=0; for(int i=1;i<=tot;++i) Ans=max(Ans,mn[i]); cout<
                 
                  <<'\n'; } return 0;}
View Code

 

P3181 [HAOI2016]找相同字符

求出每个子串在两个串中的出现次数，乘上每个点代表的不同子串个数len[p]-len[fa[p]]即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=8e5+5;char S[N>>2],T[N>>2];int id;int ch[N][26],len[N],fa[N],siz[2][N];int lst=1,tot=1;int newnode(int p,int x){ int q=ch[p][x],nq=++tot;len[nq]=len[p]+1; fa[nq]=fa[q],fa[q]=nq;memmove(ch[nq],ch[q],sizeof(ch[nq])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; return nq;}int insert(int p,int x){ if(ch[p][x]) { int q=ch[p][x]; if(len[p]+1==len[q]) { siz[id][q]=1; return q; } else { int nq=newnode(p,x); siz[id][nq]=1; return nq; } } else { int np=++tot;len[np]=len[p]+1,siz[id][np]=1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if(!p) fa[np]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[np]=q; else fa[np]=newnode(p,x); } return np; }}int cnt[N],sa[N];int main(){ scanf("%s%s",S+1,T+1); lst=1,id=0; for(int i=1;S[i];++i) lst=insert(lst,S[i]-'a'); lst=id=1; for(int i=1;T[i];++i) lst=insert(lst,T[i]-'a'); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[len[i]]--]=i; LL ans=0; for(int i=tot;i>1;--i) { siz[0][fa[sa[i]]]+=siz[0][sa[i]],siz[1][fa[sa[i]]]+=siz[1][sa[i]]; ans+=1ll*siz[0][sa[i]]*siz[1][sa[i]]*(len[sa[i]]-len[fa[sa[i]]]); } cout<
View Code

 

P3975 [TJOI2015]弦论

求出每个点后有多少串，然后按照字典序像splay一样二分出来就就可以了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=1e6+5;int t,k;char s[N>>1];int ch[N][26],len[N],fa[N],siz[N];int tot=1,lst=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1,siz[lst]=1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;len[nq]=len[p]+1;fa[nq]=fa[q],siz[nq]=0; memmove(ch[nq],ch[q],sizeof(ch[q])); fa[q]=fa[lst]=nq; for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int f[N];int cnt[N],sa[N];int main(){ scanf("%s",s+1);int n=strlen(s+1); t=read(),k=read(); for(int i=1;i<=n;++i) insert(s[i]-'a'); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;++i) sa[cnt[len[i]]--]=i; for(int i=tot;i;--i) { if(!t) siz[sa[i]]=1; else siz[fa[sa[i]]]+=siz[sa[i]]; } siz[0]=siz[1]=0; for(int i=tot;i;--i) { f[sa[i]]=siz[sa[i]]; for(int j=0;j<26;++j) f[sa[i]]+=f[ch[sa[i]][j]]; } if(f[1]
                 
                  siz[now]) { k-=siz[now]; for(int i=0;i<26;++i) { if(k>f[ch[now][i]]) k-=f[ch[now][i]]; else{putchar(i+'a');now=ch[now][i];break;} } } return 0;}
View Code

 

SP7258 SUBLEX - Lexicographical Substring Search

跟上个一样的题。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e5+5;int T,k;char s[N>>1];int ch[N][26],fa[N],len[N];int lst=1,tot=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;fa[nq]=fa[q],len[nq]=len[p]+1; memmove(ch[nq],ch[q],sizeof(ch[q])); fa[lst]=fa[q]=nq; for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int f[N],cnt[N],sa[N];int main(){ scanf("%s",s+1); for(int i=1;s[i];++i) insert(s[i]-'a'); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[len[i]]--]=i; for(int i=tot;i;--i) { f[sa[i]]=1; for(int j=0;j<26;++j) f[sa[i]]+=f[ch[sa[i]][j]]; } T=read(); while(T--) { k=read(); int now=1; while(k) { for(int i=0;i<26;++i) { if(k>f[ch[now][i]]) k-=f[ch[now][i]]; else{putchar(i+'a');now=ch[now][i];--k;break;} } } puts(""); } return 0;}
View Code

 

P4070 [SDOI2016]生成魔咒

“每个点代表的不同子串个数是len[p]-len[fa[p]]”，每次插入ans加上len[lst]-len[fa[lst]]即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define pb push_back#define pii pair
                 
                  #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e5+5;int n;LL ans=0;int a[N];map
                  
                    ch[N];int len[N],fa[N];int tot=1,lst=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;fa[nq]=fa[q],len[nq]=len[p]+1; fa[q]=fa[lst]=nq;ch[nq]=ch[q]; for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } } ans+=len[lst]-len[fa[lst]];}int main(){ n=read(); for(int i=1;i<=n;++i) { insert(read()); cout<
                   
                    <<'\n'; } return 0;}
View Code

 

BZOJ 3277 串

建广义后缀自动机，求出每个子串出现在几个串中看是否能产生贡献。每个点加上父亲的贡献，因为父亲一定会在这儿出现。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define pb push_back#define pii pair
                 
                  #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=2e5+5;int n,k;char s[N];string S[N];int ch[N][2],fa[N],len[N];int tot=1,lst;void insert(int p,int x){ lst=++tot;len[lst]=len[p]+1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;fa[nq]=fa[q],len[nq]=len[p]+1; fa[q]=fa[lst]=nq;memmove(ch[nq],ch[q],sizeof(ch[nq])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int vis[N],tims[N];void solve(string S,int x){ int now=1;int n=S.length(); for(int i=0;i
                  
                   =k)*(len[i]-len[fa[i]]); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=tot;++i) cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;++i) sa[cnt[len[i]]--]=i; for(int i=1;i<=tot;++i) sum[sa[i]]+=sum[fa[sa[i]]]; for(int i=1;i<=n;++i) query(S[i]); return 0;}
View Code

 

P4248 [AHOI2013]差异

把串倒着插入，两个子串的lcp长度就是他们在parent树上的祖先的长度。

记录每个点子树的后缀个数，计算与它父亲的其他儿子产生的贡献=siz[p]*siz[fa[p]]*len[fa[p]]。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=1e6+5;char s[N>>1];int ch[N][26],len[N],fa[N],siz[N];int lst=1,tot=1;void insert(int x){ int p=lst;lst=++tot;len[lst]=len[p]+1,siz[lst]=1; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;fa[nq]=fa[q],len[nq]=len[p]+1; fa[lst]=fa[q]=nq;memmove(ch[nq],ch[q],sizeof(ch[q])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int sa[N],cnt[N];int main(){ scanf("%s",s+1);int n=strlen(s+1); for(int i=n;i;--i) insert(s[i]-'a'); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[len[i]]--]=i; LL ans=0; for(int i=tot;i>1;--i) { ans+=1ll*siz[sa[i]]*siz[fa[sa[i]]]*len[fa[sa[i]]]; siz[fa[sa[i]]]+=siz[sa[i]]; } cout<<1ll*(n-1)*n*(n+1)/2-2*ans; return 0;}
View Code

 

P2178 [NOI2015]品酒大会

差不多和上个题一样。

两个r相似的串可以看做是从p,q开始的两个后缀的lcp长度为r。

最初ans1[r]求的是lcp恰好长为r的个数，ans2[r]求的是恰好为r的最大值。

最后再求个后缀和和后缀max就可以了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=6e5+5;const LL INF=0x3f3f3f3f3f3f3f3f;int n,a[N>>1];char s[N>>1];int ch[N][26],len[N],fa[N],siz[N];LL mx[N],mn[N];int lst=1,tot=1;void insert(int x,int v){ int p=lst;lst=++tot;len[lst]=len[p]+1,siz[lst]=1,mx[lst]=mn[lst]=v; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;len[nq]=len[p]+1,fa[nq]=fa[q]; fa[q]=fa[lst]=nq;memmove(ch[nq],ch[q],sizeof(ch[nq])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}LL ans1[N],ans2[N];int sa[N],cnt[N];int main(){ memset(ans2,-0x3f,sizeof(ans2)); memset(mx,-0x3f,sizeof(mx));memset(mn,0x3f,sizeof(mn)); n=read();scanf("%s",s+1); for(int i=1;i<=n;++i) a[i]=read(); for(int i=n;i;--i) insert(s[i]-'a',a[i]); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[len[i]]--]=i; for(int i=tot;i;--i) { ans1[len[fa[sa[i]]]]+=1ll*siz[fa[sa[i]]]*siz[sa[i]]; if(mx[sa[i]]!=-INF&&mn[sa[i]]!=INF&&mx[fa[sa[i]]]!=-INF&&mn[fa[sa[i]]]!=INF) { ans2[len[fa[sa[i]]]]=max(ans2[len[fa[sa[i]]]],1ll*mx[sa[i]]*mx[fa[sa[i]]]); ans2[len[fa[sa[i]]]]=max(ans2[len[fa[sa[i]]]],1ll*mn[sa[i]]*mn[fa[sa[i]]]); } siz[fa[sa[i]]]+=siz[sa[i]]; mx[fa[sa[i]]]=max(mx[fa[sa[i]]],mx[sa[i]]); mn[fa[sa[i]]]=min(mn[fa[sa[i]]],mn[sa[i]]); } for(int i=n-2;~i;--i) ans1[i]+=ans1[i+1],ans2[i]=max(ans2[i],ans2[i+1]); for(int i=0;i
View Code

 

CF873F Forbidden Indices

被禁止就当做没出现，否则当做出现。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define pb push_back#define pii pair
                
                 #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline int read(){ char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=4e5+5;int n;char s[N>>1],t[N>>1];int ch[N][26],len[N],fa[N];int siz[N];int tot=1,lst=1;void insert(int x,bool flag){ int p=lst;lst=++tot;len[lst]=len[p]+1,siz[lst]=flag; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;len[nq]=len[p]+1,fa[nq]=fa[q]; fa[lst]=fa[q]=nq;memmove(ch[nq],ch[q],sizeof(ch[q])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}int cnt[N],sa[N];int main(){ n=read();scanf("%s%s",s+1,t+1); for(int i=1;i<=n;++i) insert(s[i]-'a',(t[i]!='1')); for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1]; for(int i=tot;i;--i) sa[cnt[len[i]]--]=i; for(int i=tot;i;--i) siz[fa[sa[i]]]+=siz[sa[i]]; LL ans=0; for(int i=1;i<=tot;++i) ans=max(ans,1ll*len[i]*siz[i]); cout<
View Code

 

CodeChef Killjee and k-th letter

做不下去了， 还没有看懂它建后缀树的地方，等待zbq解答ing..

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define pb push_back#define pii pair
                 
                  #define mp make_pair#define fi first#define se second#define lb lower_bound#define ub upper_boundusing namespace std;typedef long long LL;typedef unsigned long long ULL;inline LL read(){ char c=getchar();LL num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f;}const int N=4e5+5;int n;LL sum[N];char s[N>>1];int son[N][26];int ch[N][26],len[N],fa[N],rig[N],pos[N];int lst=1,tot=1;void insert(int x,int i){ int p=lst;lst=++tot;len[lst]=len[p]+1;++rig[lst],pos[lst]=i; for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=lst; if(!p) fa[lst]=1; else { int q=ch[p][x]; if(len[p]+1==len[q]) fa[lst]=q; else { int nq=++tot;fa[nq]=fa[q],len[nq]=len[p]+1; fa[q]=fa[lst]=nq;memmove(ch[nq],ch[q],sizeof(ch[nq])); for(;ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }}void prework(){ static int cnt[N],sa[N]; for(int i=1;i<=tot;++i) ++cnt[len[i]]; for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;++i) sa[cnt[len[i]]--]=i; for(int i=tot,x,y;i;--i) { x=sa[i],y=fa[sa[i]]; rig[y]+=rig[x],pos[y]=pos[x]; son[y][s[pos[x]-len[y]]-'a']=x; }}int dfn[N],bound;void dfs(int u){ dfn[++bound]=u; for(int i=0;i<26;++i) if(son[u][i]) dfs(son[u][i]);}LL calc(int l,int r){ return 1ll*(l+r)*(r-l+1)/2;}int query(LL k){ int l=1,r=tot,mid; while(l<=r) { mid=(l+r)>>1; if(sum[mid]
                  
                   >1; if(1ll*rig[t]*calc(h,mid)
View Code

 

转载于:https://www.cnblogs.com/lovewhy/p/10704390.html

你可能感兴趣的文章
我的工作内容
查看>>
12_文件查找详解和特殊权限
查看>>
Linux基础初识（五）
查看>>
2. 组建的注册与引入
查看>>
Excel 相关实用计算公式
查看>>
1169.比较奇偶数个数
查看>>
Java – How to convert Array to Stream
查看>>
java学习1-环境搭建
查看>>
c# 获取当前季的第一天以及最后一天
查看>>
MYSQL生成两个日期之间的所有日期数据
查看>>
shell脚本安装jdk
查看>>
( 转)Sqlserver中tinyint, smallint, int, bigint的区别 及 10进制转换16进制的方法
查看>>
ASP.NET实现类似Excel的数据透视表
查看>>
js在IE与firefox的差别。。。
查看>>
数据库事务的四大特性以及事务的隔离级别
查看>>
html4与html5的区别及html5的一些新特性
查看>>
2018年牛客多校算法寒假训练营练习比赛（第一场）C. 六子冲
查看>>
版本工具管理之----git
查看>>
JavaEE基础（二十四）/多线程
查看>>
利用httpd.ini和.htaccess的Rewrite实现301域名重定向
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-13 04:20:21   当前IP: 18.217.122.161   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我