注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj1226】【后缀数组】【Substrings】  

2014-04-13 17:50:26|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出n个字符串,求在每个字符串或其翻转串 都出现的最长子串

    0.0做法比较裸恩...先把n个字符串+n个字符串的反串用分隔符号连接,然后求一遍后缀数组,咱们再二分答案并且分组(注意二分的上界是所有字符串中最短的那个。那么咱们的目的就是找到这样一个组,
    1)它的所有字符串的长度在合法范围内。
    2)每一个字符串都至少出现在这里一次。
    然后第一个咱们需要记录下原字符串的每个字符串出现的位置,然后判断就是 当前位置在某个字符串内且当前位置+二分长度在当前位置。
    然后第二个类似,咱们用一个HASH表来表示某个字符串是否出现,然后这样子就只需要扫一遍O(n)的了,综复杂度为O(nlogn)。

    0.0其实是来复习后缀数组的,所以咱把一些后缀数组感想写下来。
    后缀数组是将后缀排序之后的数组,即SA,然后求法是先对第二个关键字排序,然后再对第一个关键字排序,一开始需要对第一个关键字排一次序,排序使用的是计数排序。计数排序实际上是这样的....

    for (i=1;i<=n;i++) c[a[i]]++
    for (i=1;i<=m;i++) c[i]+=c[i-1];
    for (i=n;i>0;i--) sa[--c[a[i]]]=i;

     它的扩展就是基数排序。
     咱们可以发现基数排序实际上就是在不改变原来的相同元素的顺序的情况下,以元素为关键字进行排序。也就是这里的重点是不改变原来的相同元素的顺序。所以假设有两个关键字,咱们以第二个关键字排了序,然后再按第二个关键字的顺序用计数排序对第一个关键字排序的话,就会发现对于第一个关键字相同的,第二个关键字是按递增排序的!这个其实就是这里基数排序的正确性的原因,所以咱们一开始需要一个计数排序来初始化。

   然后就是height数组的计算。这里设h[i]=height[rank[i]],则有 h[i]>=h[i-1]-1,这个可以使得height数组的计算变成线性的。

   然后本题最囧的地方在于这里的字符串是可以包含数字字母等乱七八糟的东西的,一开始以为只有字母WA了半天233..
    
=======================================

program poj1226;
const maxn=60010;
var ws,r,sa,rank,height:array[0..maxn]of longint;
    x:array[0..1,0..maxn]of longint;
    st,ed:array[0..maxn]of longint;
    hash:array[0..maxn]of int64;
    n,tot,t,tt:longint;
    s:ansistring;

procedure calsa(n,m:longint);
var w,j,p,i:longint;
begin
  w:=0;p:=0;j:=1;
  fillchar(ws,sizeof(ws),0);
  fillchar(x,sizeof(x),0);
  for i:=1 to n do inc(ws[r[i]]);
  for i:=1 to m do inc(ws[i],ws[i-1]);
  for i:=n downto 1 do
   begin
     dec(ws[r[i]]);
     sa[ws[r[i]]]:=i;
   end;
  for i:=1 to n do x[w][i]:=r[i];
  while j<=n do
   begin
     for i:=n-j+1 to n do
      begin
        inc(p);
        x[w xor 1][p]:=i;
      end;
     for i:=0 to n-1 do
      if sa[i]>j then
       begin
         inc(p);
         x[w xor 1][p]:=sa[i]-j;
       end;
      fillchar(ws,sizeof(ws),0);
      for i:=1 to n do inc(ws[x[w][x[w xor 1][i]]]);
      for i:=1 to m do inc(ws[i],ws[i-1]);
      for i:=n downto 1 do
       begin
         dec(ws[x[w][x[w xor 1][i]]]);
         sa[ws[x[w][x[w xor 1][i]]]]:=x[w xor 1][i];
       end;
      w:=w xor 1;p:=1;x[w][sa[0]]:=0;
      for i:=1 to n-1 do
       if (x[w xor 1][sa[i]]=x[w xor 1][sa[i-1]])and
          (x[w xor 1][sa[i]+j]=x[w xor 1][sa[i-1]+j])then
           x[w][sa[i]]:=x[w][sa[i-1]]
          else
           begin
             inc(p);
             x[w][sa[i]]:=x[w][sa[i-1]]+1;
           end;
      if p>=n then break;
      m:=p;p:=0;j:=j shl 1;
   end;
end;

procedure calheight(n:longint);
var i,j,k:longint;
begin
  for i:=1 to n do rank[sa[i]]:=i;
  k:=0;
  for i:=1 to n do
   begin
     if k<>0 then dec(k);
     j:=sa[rank[i]-1];
     while r[i+k]=r[j+k] do inc(k);
     height[rank[i]]:=k;
   end;
end;

function find(pos:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=n;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if (st[mid]<=pos)and(ed[mid]>=pos)then exit(mid);
     if (st[mid]>pos) then r:=mid-1
                      else l:=mid+1;
   end;
  exit(l);
end;

procedure init;
var i,j,k,rr,ll,mid,time,num,sign:longint;
    flag:boolean;
begin
  readln(n);
  tot:=0;rr:=maxlongint;
  fillchar(st,sizeof(st),0);
  fillchar(ed,sizeof(ed),0);
  fillchar(r,sizeof(r),0);
  sign:=129;
  for i:=1 to n do
   begin
     readln(s);
     k:=length(s);
     if rr>k then rr:=k;
     st[i]:=tot+1;
     for j:=1 to k do
      begin
        inc(tot);
        r[tot]:=ord(s[j]);
      end;
     inc(tot);
     r[tot]:=sign;
     inc(sign);
     for j:=k downto 1 do
      begin
        inc(tot);
        r[tot]:=ord(s[j]);
      end;
     inc(tot);
     r[tot]:=sign;
     inc(sign);
     ed[i]:=tot;
   end;
  r[tot]:=0;
  if n=1 then
   begin
     write(tot shr 1-1);
     exit;
   end;
  fillchar(sa,sizeof(sa),0);
  calsa(tot,sign+1);
  fillchar(rank,sizeof(rank),0);
  fillchar(height,sizeof(height),0);
  calheight(tot-1);
  ll:=0;
  while ll<rr do
   begin
     fillchar(hash,sizeof(hash),0);
     mid:=(ll+rr+1)shr 1;
     i:=1;time:=0;
     flag:=false;
     while i<tot-1 do
      begin
        j:=i;inc(time);num:=n;
        while (j<tot-1)and(height[j+1]>=mid)do
         begin
           k:=find(sa[j]);
           if hash[k]<>time then dec(num);
           hash[k]:=time;
           if j<>1 then
            begin
             k:=find(sa[j+1]);
             if hash[k]<>time then dec(num);
             hash[k]:=time;
            end;
           inc(j);
         end;
        i:=j+1;
        if num=0 then
         begin
          flag:=true;
          break;
         end;
      end;
     if flag then ll:=mid
             else rr:=mid-1;
   end;
  write(ll);
end;

begin
  readln(tt);
  for t:=1 to tt do
   begin
    init;
    if t<>tt then writeln;
   end; 
end.



  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017