随笔-38  评论-23  文章-0  trackbacks-0


/*初看这题 以为是传统意义上的最长重复子串.其实不然,看例子就明白*/

接触这题后才开始看Suffix_array的资料.一篇论文,里面谈到如何使用O(nlogn)的方法构造后缀数组SA.并且用0(nlongn)的方法构造height数组. 点击下载后缀数组论文
以下代码写的有点粗糙..排序上其实可以优化很多.我只使用sort()进行排序 惭愧.....

#include<iostream>
#include
<string>
#include
<algorithm>
using namespace std;
#define N 200000
int sa[N];
int rank[N];
int lrank[N],h[N],height[N];
int k;
char str[50005];
bool cmpchar(const int& a,const int& b)
{
    
return str[a]<str[b];
}

bool cmprank(const int&a ,const int&b)
{
    
return rank[a]<rank[b]||(rank[a]==rank[b]&&rank[a+k]<rank[b+k]);
}

bool equ(const int& a,const int& b)
{
    
return lrank[a]==lrank[b]&&lrank[a+k]==lrank[b+k];
}

void createSA(int len)
{
    
int i=0;
    
for(i=0;i<len;i++)
        sa[i]
=i;
    sort(sa,sa
+len,cmpchar);
    
//SA(1) 每个后缀的首字母有关。这里其实可以采用计数排序
    
//rank(1) 根据SA(1)求得的排名数组
    for(rank[sa[0]]=0,i=1;i<len;i++)
    
{
        rank[sa[i]]
=rank[sa[i-1]];
        
if(str[sa[i]]!=str[sa[i-1]])
            rank[sa[i]]
++;
    }

    
//在SA(1)基础上扩展到SA(2^k) ->(2^k>=len)
    for(k=1;k<len;k*=2)
    
{
        
//根据Rank(k)数组求SA(2k)
        
//Suffix(i)<=(2k)Suffix(j) 等价于Rank(i)<(k)Rank(j)||Rank(i)==(k)Rank(j)&&Rank(i)<(i+k)Rank(j+k)
        sort(sa,sa+len,cmprank);
        
for(i=0;i<len;i++)
            lrank[i]
=rank[i];
        
//根据SA(2k) 求Rank(2k)
        for(rank[sa[0]]=0,i=1;i<len;i++)
        
{
            rank[sa[i]]
=rank[sa[i-1]];
            
if(!equ(sa[i],sa[i-1]))
                rank[sa[i]]
++;
        }

    }

}


void gethei(int len)
{
    
int i=0,d=0,j,s;
    memset(h,
0,sizeof(h));
    
//height[i]=LCP(i-1,i)
    for(i=0;i<len;i++)
    
{
        
if(rank[i]==0)
        
{
            h[rank[i]]
=0;
            
continue;
        }

        j
=rank[i]-1;
        d
=rank[i];
        
//Suffix(Rank[i])与Suffix(Rank[i-1]比较相等的字符个数
        
// i==0或者h[i-1]<=1则从头开始比较两个后缀
        
//否则的话表示已经有前h[i-1]-1个字符相等 继续比较后面相等字符的个数
        if(i==0||h[i-1]<=1)
            s
=0;
        
else
            s
=h[i-1]-1;
        
for(;sa[d]+s<len&&sa[j]+s<len;s++)
            
if(str[sa[d]+s]!=str[sa[j]+s]) break;
        h[i]
=s;
        
//其实可以根据height[rank[i]]=h[i]求height[]这样可以省去h[]数组空间
    }

    
//heigth[i]=h[sa[i]]
    for(i=0;i<len;i++)
        height[i]
=h[sa[i]];

    
}

int main()
{
    
int t;
    cin
>>t;
    getchar();
    
while(t--)
    
{
        gets(str);
        
int len=strlen(str);
        str[len
++]='$';
        str[len]
=0;
        createSA(len);
        gethei(len);
        
int maxid=height[0];
        
for(int i=1;i<len;i++)
        
{
            
int l1=sa[i],l2=sa[i-1];
            
//因为height[i]表示LCP(i-1,i)
            
//而题目要求得连续重复的,则只要具有最长公共前缀是连续的
            
//Suffix(SA[l1])和Suffix(SA[l2])的最长公共前缀是连续 即l1+heigt[i]==l2
            if(l1>l2)
                swap(l1,l2);
            
if(l1+height[i]==l2&&height[i]>maxid)
                maxid
=height[i];
        }

        cout
<<maxid<<endl;
    }

    
return 0;
}


 因为zoj数据弱了 其实以上代码不能过评论的那组数据。是我考虑欠缺了..现修改main函数通过枚举结果值来计算。不过感觉太耗时间了 可否有更好的方法?修改main函数代码如下:

bool check(int k,int len)
{
    
int i,j,a,b;
    
for(i=0;i<len;i++)
    
{
        
if(height[i]>=k) //枚举大于等于k的区间里 只要存在连续段就是结果.
        {
            a
=sa[i-1];
            
for(j=i;j<len&&height[j]>=k;j++)
            
{
                b
=sa[j];
                
if(a+height[j]==b||b+height[j]==a)
                    
return true;
            }

        }

    }

    
return false;
}

int main()
{
    
int t;
    cin
>>t;
    getchar();
    
while(t--)
    
{
        gets(str);
        
int len=strlen(str);
        str[len
++]='$';
        str[len]
=0;
        createSA(len);
        gethei(len);
        
int maxid;
        
//这样枚举太耗时间了。不知可有更好的方法?
        for(maxid=len/2;maxid>=0;maxid--)
        
{
            
if(check(maxid,len))
                
break;
        }

        cout
<<maxid<<endl;
    }

    
return 0;
}




 

posted on 2009-05-09 11:22 米游 阅读(1653) 评论(5)  编辑 收藏 引用 所属分类: ACM

评论:
# re: 使用后缀数组 解决zoj 3199 Longest Repeated Substring 2009-05-12 14:19 | [NKU]Angel
void gethei(int len)
{
int i=0,d=0,j,s;
memset(h,0,sizeof(h));
//height[i]=LCP(i-1,i)
for(i=0;i<len;i++)
{
if(rank[i]==0)
{
h[rank[i]]=0;//←这个地方应该是h[i]=0吧。。
continue;
}
j=rank[i]-1;
d=rank[i];
//Suffix(Rank[i])与Suffix(Rank[i-1]比较相等的字符个数
// i==0或者h[i-1]<=1则从头开始比较两个后缀
//否则的话表示已经有前h[i-1]-1个字符相等 继续比较后面相等字符的个数
if(i==0||h[i-1]<=1)
s=0;
else
s=h[i-1]-1;
for(;sa[d]+s<len&&sa[j]+s<len;s++)
if(str[sa[d]+s]!=str[sa[j]+s]) break;
h[i]=s;
//其实可以根据height[rank[i]]=h[i]求height[]这样可以省去h[]数组空间
}
//heigth[i]=h[sa[i]]
for(i=0;i<len;i++)
height[i]=h[sa[i]];


}
  回复  更多评论
  
# re: 使用后缀数组 解决zoj 3199 Longest Repeated Substring 2009-05-13 10:39 | 米游
@[NKU]Angel
谢谢指点..的确是那样的..  回复  更多评论
  
# re: 使用后缀数组 解决zoj 3199 Longest Repeated Substring 2009-05-13 10:40 | 米游
谢谢指点..的确是那样的..@[NKU]Angel
  回复  更多评论
  
# re: 使用后缀数组 解决zoj 3199 Longest Repeated Substring 2009-05-16 01:36 | scut_solar
在网上找了该题的题解,发现很多人用的都是和你一样的解法,但是最后我发现这种结果有问题
例如:defgdefgzdefge
答案应该是4吧,但是用这种方法解的答案是0  回复  更多评论
  
# re: 使用后缀数组 解决zoj 3199 Longest Repeated Substring 2009-05-16 14:57 | 米游
@scut_solar
求解那里出了问题..需要枚举了应该  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理