poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津预选题

题目：http://poj.org/problem id=1226

http://acm.hdu.edu.cn/showproblem.php pid=1238

其实用hash+lcp可能也可以，甚至可能写起来更快，不过我没试，我最近在练习后缀数组，所以来练手

后缀数组的典型用法之一----------------后缀数组+lcp+二分

思路：1、首先将所有的字符串每读取一个，就将其反转，作为一组，假设其下标为i到j，那么cnt[i]到cnt[j]都标记为一个数字（这个数字意思是第几个读入的字符串）

2、注意将字符串及其反串用一个未出现的字符隔开，我用的'\0'

3、二分答案，二分判断是不是合法的函数我折腾了很久...

lcp的时候 一个非常容易错的地方---不要把你加的空字符也算上

    for(int i=0;i
  
   0)h--;
        for(;j+h
   
    
 
    





 
    

 
 
    
最终是这么写的：
 
    
 
 
    
int C(int x)
{
    memset(sea,0,sizeof(sea));
    int num=0,ret=0,last=0;
    for(int i=ns*2;i
     
      i=ns*2,因为开始ns*2-1个都是空字符
    {
        if(lcp[i]>=x)  //lcp的定义好好看看，里面的后缀本身就是按字典序的，所以
      lcp[i]>=x能保证连着的这几个后缀的公共前缀相同
        {
            sea[cnt[sa[i]]]=sea[cnt[sa[i+1]]]=1;
        }
        else
       //看是不是合法，不合法就重新计数
        {
            for(int i=0;i<=ns;i++)
                if(sea[i])ret++;
            if(ret>=ns)
            {
                return 1;
            }
            else ret=0;
            memset(sea,0,sizeof(sea));
        }
    }
    for(int i=0;i<=ns;i++)
        if(sea[i])ret++;
    if(ret>=ns)return 1;
    else return 0;
}

     
做这题花了很久，但是基本没参考题解，基本完全是自己做的，感觉不错 
    
 
    
学到了：
 1、读取s将s反转存到同一个数组里，写法还是蛮锻炼代码能力的
 
    
2、C的写法-------因为后缀数组+lcp+二分非常广泛，
 
    

 
 
    

 
 
    
 
    
#include 
     
      
#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             const int MAXN =20200; using namespace std; int n,k,alen,rkcnt,ns;//n=strlen(s); int rk[MAXN],tmp[MAXN],sa[MAXN],lcp[MAXN],cnt[MAXN],sea[120];//rank为c++的保留字，所以rk代之,cnt记录术语第几个 char s[MAXN]; char str[101][101]; bool cmpSa(int i,int j) { if(rk[i] != rk[j])return rk[i]
            
             0)h--; for(;j+h
             
              =x) { sea[cnt[sa[i]]]=sea[cnt[sa[i+1]]]=1; } else { for(int i=0;i<=ns;i++) if(sea[i])ret++; if(ret>=ns) { return 1; } else ret=0; memset(sea,0,sizeof(sea)); } } for(int i=0;i<=ns;i++) if(sea[i])ret++; if(ret>=ns)return 1; else return 0; } int main() { //freopen("hdu 1238.txt","r",stdin); int ncase,len,ii,j,maxlen; scanf("%d",&ncase); while(ncase--) { alen=len=maxlen=rkcnt=0; scanf("%d",&ns); for(int i=0;i
              
               =0 && s[ii];j++,ii--) { s[j]=s[ii]; } s[j]=s[ii]='\0'; alen+=len; } alen--; s[alen]='\0'; int flag=0; for(int i=0;i<=alen;i++) { cnt[i]=rkcnt; if(!s[i]) { flag=!flag; if(!flag)rkcnt++; } } n=alen; construct_sa(); construct_lcp(); int d=0,up=101,mid=101; /*二分上限的选取*/ while(up>1+d) { mid=(up+d)/2; if(C(mid))d=mid; else up=mid; } printf("%d\n",d); } return 0; } 
              
             
            
           
          
         
        
       
      
     
随后我会对后缀数组结合自己的做题还有国家集训队论文写个总结