首页 > 代码库 > 【BZOJ4650&UOJ219】优秀的拆分(二分,hash)
【BZOJ4650&UOJ219】优秀的拆分(二分,hash)
题意:
思路:
在实现时SA可以用hash+二分代替,会多一个log
BZ上跑的飞快,但UOJ上extra卡出翔,已经放弃
不过转C或者写SA没准就过了
看来转C迫在眉睫
1 const mo=700103; 2 var f,g:array[0..100000]of int64; 3 h,mi:array[0..100000]of int64; 4 v,cas,i,n,j,x,y:longint; 5 ans:int64; 6 ch:ansistring; 7 8 function min(x,y:longint):longint; 9 begin 10 if x<y then exit(x); 11 exit(y); 12 end; 13 14 function hash(x,y:longint):longint; 15 begin 16 hash:=(h[y]-h[x-1]*mi[y-x+1] mod mo+mo) mod mo; 17 end; 18 19 function lcp(x,y:longint):longint; 20 var l,r,mid,last:longint; 21 begin 22 l:=1; r:=min(i,min(n-x+1,n-y+1)); last:=1; 23 while l<=r do 24 begin 25 mid:=(l+r)>>1; 26 if hash(x,x+mid-1)=hash(y,y+mid-1) then begin last:=mid; l:=mid+1; end 27 else r:=mid-1; 28 end; 29 exit(last); 30 end; 31 32 function lcs(x,y:longint):longint; 33 var l,r,mid,last:longint; 34 begin 35 l:=1; r:=min(i,min(x,y)); last:=1; 36 while l<=r do 37 begin 38 mid:=(l+r)>>1; 39 if hash(x-mid+1,x)=hash(y-mid+1,y) then begin last:=mid; l:=mid+1; end 40 else r:=mid-1; 41 end; 42 exit(last); 43 end; 44 45 begin 46 47 mi[0]:=1; 48 for i:=1 to 50000 do mi[i]:=mi[i-1]*6662333 mod mo; 49 readln(cas); 50 for v:=1 to cas do 51 begin 52 readln(ch); 53 n:=length(ch); 54 for i:=0 to n+1 do 55 begin 56 f[i]:=0; g[i]:=0; h[i]:=0; 57 end; 58 for i:=1 to n do h[i]:=(h[i-1]*6662333+ord(ch[i])-ord(‘a‘)+1) mod mo; 59 for i:=1 to (n+1) div 2 do 60 begin 61 j:=1; 62 while j<=n do 63 begin 64 if j+i>n then break; 65 if (ch[j]<>ch[j+i]) then begin j:=j+i; continue; end; 66 x:=lcp(j,j+i); y:=lcs(j,j+i); 67 // x:=min(x,i); y:=min(y,i); 68 if x+y>i then 69 begin 70 inc(g[j-y+1]); dec(g[j+x-i+1]); 71 inc(f[j+i-y+i]); dec(f[j+i+x]); 72 end; 73 j:=j+i; 74 end; 75 end; 76 ans:=0; 77 for i:=1 to n do f[i]:=f[i-1]+f[i]; 78 for i:=1 to n do g[i]:=g[i-1]+g[i]; 79 for i:=1 to n-1 do ans:=ans+f[i]*g[i+1]; 80 writeln(ans); 81 end; 82 83 end. 84
【BZOJ4650&UOJ219】优秀的拆分(二分,hash)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。