BNUOJ 34990 北京邀请赛最后一题 - c++编程基础

TOP

BNUOJ 34990 北京邀请赛最后一题

2015-07-20 17:45:42 来源: 作者: 【大中小】浏览:1次

思路：这题看了题解说是后缀数组做的，然后自己就偿试了一下，唉……没想到不管是不管是倍增算法的后缀还是DC3算法的后缀都T了，实在无计可施了，可能只有哗然可以过了。不过比赛那天题解说是没有卡后缀的。只是比赛那天自己还不会后缀数组，所以这题自己根本就没有看到。因为后缀自己练得还比较少，这题正好用RMQ求任意两个后缀之间的最长公共前缀，所以自己就拿这题练手了，虽然T了，但是倍增的算法和DC3的算法都贴上来吧，以配以后可能用得到。

倍增算法的代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 10000005 typedef long long ll; typedef unsigned long long ull; using namespace std; void radix(int *str,int *a,int *b,int n,int m) { static int count[maxn]; mem(count,0); for(int i=0; i
           
            =0; i--) b[--count[str[a[i]]]]=a[i]; } void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa { static int rank[maxn],a[maxn],b[maxn]; for(int i=0; i
            
             =n?0:rank[j+(1<
             
              r) swap(l,r); l++; //为什么要加1呢，因为l是与l+1位置求的最长公共前缀 //即height[l+1]=suffix(l+1)与suffix(l)的最长公共前缀 int k=log(r-l+1.0)/log(2.0); return min(dp[l][k],dp[r-(1<
              
               =len) return true; return false; } int main() { int t,ii=1; scanf("%d",&t); while(t--) { scanf("%s%s",s,ss); int l1=strlen(s),l2=strlen(ss); if(l1
               
                
 
                 
                DC3算法的代码： 
                
                #pragma comment(linker, "/STACK:1024000000,1024000000")
#include
                 
                  
#include
                  
                    #include
                   
                     #include
                    
                      #include
                      #include
                      
                        #include
                       
                         #include
                        
                          #include
                         
                           #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 10000005 #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)
                          
                           =0; i--) b[--wt[wv[i]]]=a[i]; return; } void dc3(int *r,int *sa,int n,int m) { int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; r[n]=r[n+1]=0; for(i=0; i
                           
                            r) swap(l,r); l++; //为什么要加1呢，因为l是与l+1位置求的最长公共前缀 //即height[l+1]=suffix(l+1)与suffix(l)的最长公共前缀 int k=log(r-l+1.0)/log(2.0); return min(dp[l][k],dp[r-(1<
                            
                             =len) return true; return false; } int main() { int t,ii=1; scanf("%d",&t); while(t--) { scanf("%s%s",s,ss); int l1=strlen(s),l2=strlen(ss); if(l1


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++11 thread::detach(2)	下一篇：NYOJ-数的长度

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: