poj 3882（Stammering Aliens）后缀数组或者 hash

后缀数组：构建后缀数组，注意要在字符串莫末尾加上一个没出现过的字符。然后可以2分或者直接扫描，直接扫描需要用单调队列来维护

VIEW CODE

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; const int mmax= 40010; const int mod=1000000007; typedef long long LL; //typedef unsigned long long ULL; char s[mmax]; int sa[mmax],t[mmax],t2[mmax],c[mmax],n; void build_sa(int m) { int i,*x=t,*y=t2; for(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; } } int rank[mmax],heigth[mmax]; void getheigth() { for(int i=0;i
                   
                    head && heigth[len[end-1]]>= heigth[i]) end--; len[end++]=i; while(end1>head1 && sa[mark[end1-1]] 
                    
                     head && heigth[len[end-1]]>= heigth[i]) end--; len[end++]=i; if(i-m==mark[head1]) head1++; while(end1>head1 && sa[mark[end1-1]] 
                     
                      ans) { ans=heigth[len[head]]; e=sa[mark[head1]]; } else if(heigth[len[head]]==ans) e=max(e,sa[mark[head1]]); } if(ans==0) { puts("none"); continue; } printf("%d %d\n",ans,e); } return 0; }

字符串hash ：直接2分了很好写的

VIEW CODE

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; const int mmax= 1000010; const int mod=1000000007; const int inf=0x3fffffff; using namespace std; typedef long long LL; typedef unsigned long long ULL; ULL H[mmax]; map
               
                q; int m; char str[mmax]; ULL Pow[mmax]; void build_ha() { int n=strlen(str); H[n]=0; for(int i=n-1;i>=0;i--) H[i]=H[i+1]*131+str[i]; } ULL Ha[mmax]; bool ok(int k) { int n=strlen(str); for(int i=0;i+k-1
                
                 =m) return 1; cnt=1; } } if(cnt>=m) return 1; return 0; } int main() { Pow[0]=1; for(int i=1;i
                 
                  >m&&m) { scanf("%s",str); int n=strlen(str); int l=1,r=n+1; build_ha(); while(l
                  
                   >1; if(ok(mid)) l=mid+1; else r=mid; } int ans=r-1; if(!ans) { puts("none"); continue; } int e; q.clear(); for(int i=0;i+ans-1
                   
                    =m) e=i; } printf("%d %d\n",ans,e); } return 0; }

poj 3882（Stammering Aliens） 后缀数组 或者 hash