一些字符串的题-白红宇

一些字符串的题

阅读量：5324 次

发布时间：2019-06-14

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

1.BZOJ 2434 阿狸的打字机

AC自动机+树状数组

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             using namespace std;const int maxn=100000+29;char s[maxn];int tot,n,m,ecnt,fi[maxn],nx[maxn],tt[maxn],fir[maxn],nxt[maxn],to[maxn];int ls[maxn],le[maxn],dfs_clock,sum[maxn],cnt,num[maxn],ans[maxn],xbh[maxn];int qry(int x){ int res=0; for(int i=x;i>0;i-=(i&(-i))) res+=sum[i]; return res;} void addsum(int x,int v){ for(int i=x;i<=tot;i+=(i&(-i))) sum[i]+=v;}struct Node{ int l,r,id,bh;}qs[maxn];struct node{ node *s[26],*fail,*fa; int id,bh; node(){ for(int i=0;i<26;i++) s[i]=NULL; fail=NULL; fa=NULL; }}*root,*now,*tep;void add(int u,int v,int k){ nx[++ecnt]=fi[u];fi[u]=ecnt;tt[ecnt]=v; num[ecnt]=k;}void add_edge(int u,int v){ nxt[++cnt]=fir[u]; fir[u]=cnt; to[cnt]=v;}void build(){ root=new node(); root->bh=++tot; now=root; for(int i=0;s[i]!='\0';i++){ if(s[i]=='P') {now->id=++n; xbh[n]=tot; } else if(s[i]=='B') now=now->fa ; else{ int c=s[i]-'a'; if(now->s[c]==NULL){ tep=new node(); tep->bh=++tot; now->s[c]=tep; now->s[c]->fa=now; } now=now->s[c]; } }}void dfs(int x){ ls[x]=++dfs_clock; for(int i=fir[x];i;i=nxt[i]){ dfs(to[i]); } le[x]=dfs_clock;}int query(int x){ return qry(le[x])-qry(ls[x]-1);}void get_fail(){ queue
            
             que; que.push(root); while(!que.empty() ){ now=que.front(); que.pop(); for(int i=0;i<26;i++) if(now->s[i]!=NULL){ if(now==root) now->s[i]->fail=root; else{ tep=now->fail; while(tep->s[i]==NULL&&tep->fail!=NULL) tep=tep->fail; if(tep->s[i]) now->s[i]->fail =tep->s[i]; else now->s[i]->fail=root; } add_edge(now->s[i]->fail->bh,now->s[i]->bh); que.push(now->s[i]); } }}void travel(){ now=root; for(int i=0;s[i]!='\0';i++){ if(s[i]=='P') { if(fi[now->id]){ for(int j=fi[now->id];j;j=nx[j]){ ans[num[j]]=query(xbh[tt[j]]); } } } else if(s[i]=='B') {addsum(ls[now->bh],-1); now=now->fa ;} else{ int c=s[i]-'a'; now=now->s[c]; addsum(ls[now->bh],1); } }}int main(){ scanf("%s",s); build(); get_fail(); dfs(1); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&qs[i].l,&qs[i].r); add(qs[i].r,qs[i].l,i); qs[i].id=i; } travel(); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0;}

BZOJ 2434 阿狸的打字机

2.hash UVA 4513口吃的外星人

紫书原题

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              const int maxn=4e5+29;const int x=123;char s[maxn];int pos,m,ans,n,rak[maxn],hs[maxn],xl[maxn],has[maxn];using namespace std;bool cmp(const int &a,const int &b){ return has[a]==has[b]?a
              
               
                =m) pos=max(pos,rak[i]); } return pos>-1;}int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); while(scanf("%d",&m)){ if(!m) break; scanf("%s",s); n=strlen(s); hs[n]=0; for(int i=n-1;i>=0;i--) hs[i]=hs[i+1]*x+(s[i]-'a'); xl[0]=1; for(int i=1;i<=n;i++) xl[i]=xl[i-1]*x; if(!check(1)) printf("none\n"); else{ int l=1,r=n+1; while(r-l>1){ int mid=l+((r-l)>>1); if(check(mid)) l=mid; else r=mid; } check(l); printf("%d %d\n",l,pos); } } return 0;}

口吃的外星人

3.BZOJ 2342 双倍回文

manacher 没想开手写了一颗treap

BZOJ 2342 双倍回文

4.BZOJ 3230 相似子串

后缀数组

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn=100000+50;typedef long long LL; //LL真的害死人啊 int m=150,n,Q,saz[maxn],saf[maxn],rakz[maxn],rakf[maxn];int hz[maxn],hf[maxn],stz[maxn][20],stf[maxn][20];char ch[maxn],sz[maxn*2],sf[maxn*2];LL sum[maxn];inline bool mp(int *y,int p,int q,int k){ int o0=p+k>=n?-1:y[p+k]; int o1=q+k>=n?-1:y[q+k]; return o0==o1&&y[p]==y[q];}void make_hight(char *s,int *hight,int *sa,int st[][20],int *rank){ for(int i=0;i
              
               =0;i--) sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){ int p=0; for(i=n-k;i
               
                =k) y[p++]=sa[i]-k; for(i=0;i
                
                 =0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y);p=1;x[sa[0]]=0; for(i=1;i
                 
                  =n) break; m=p; } make_hight(s,hight,sa,st,rank);}void make_sum(){ sum[0]=n-saz[0]; for(int i=1;i
                  
                   >1; if(sum[mid-1]>=x) rel=mid-1,r=mid-1; else l=mid+1; } rer=n-(sum[rel]-x)-1; rel=saz[rel];}LL RMQ(int st[][20],int *sa,int l,int r){ int k=0; if(l==r) return n-sa[l]; while(l+(1<
                   
                    <=r) k++; if(k) k--; return (LL)min(st[l][k],st[r-(1<
                    
                     l2) swap(l1,l2); ans1=min(ans1,RMQ(stz,saz,l1,l2)); r1=rakf[n-r1-1]; r2=rakf[n-r2-1]; if(r1>r2) swap(r1,r2); ans2=min(ans2,RMQ(stf,saf,r1,r2)); return ans1*ans1+ans2*ans2;}int main(){ scanf("%d%d",&n,&Q); scanf("%s",sz); for(int i=0;i
                     
                      sum[n-1]||qr>sum[n-1]) printf("-1\n"); else printf("%lld\n",qry(ql,qr)); } return 0;}

BZOJ 3230 相似子串

5.BZOJ 3238 差异

后缀数组单调栈优化

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
                const int maxn=100000+5;typedef long long LL;char s[maxn];int mi=1e9+7,m=150,n,sa[maxn],hight[maxn],rank[maxn],l[maxn],r[maxn];using namespace std;void make_hight(){ for(int i=0;i
               
                =n?-1:y[a+k]; int o2=(b+k)>=n?-1:y[b+k]; return (o1==o2&&y[a]==y[b]);}void make_sa(){ static int t1[maxn],t2[maxn],c[maxn]; int *x=t1,*y=t2,i,k; for(i=0;i
                
                 =0;i--) sa[--c[x[i]]]=i; for(k=1;k<=n;k<<=1){ int p=0; for(i=n-k;i
                 
                  =k) y[p++]=sa[i]-k; for(i=0;i
                  
                   =0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1; x[sa[0]]=0; for(i=1;i
                   
                    =n) break; m=p; } make_hight();}LL work(){ LL ans=0,res=0; int now; for(int i=n;i>=1;i--){ ans+=(LL)i*(LL)(n-1); } stack
                    
                     que; que.push(0); for(int i=1;i
                     
                      hight[i])){ que.pop(); } if(!que.empty()){ now=que.top(); l[i]=now; } else l[i]=-1; que.push(i); } while(!que.empty()) que.pop(); for(int i=n-1;i>0;i--){ while(!que.empty()&&(hight[now=que.top()]>=hight[i])){ que.pop(); } if(!que.empty()){ now=que.top(); r[i]=now; } else r[i]=n; que.push(i); } for(int i=0;i