Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次做hash,哪位大牛能给点提示吗?

Posted by yuanyirui at 2007-07-02 10:31:33 on Problem 1200
如果用bool做哈希表记录有没有出现过的子串,有效的空间要NC^N个。
如果想提高速度用移位:
字符种数是2,用1位记录一个字符的权,log2(16000000)=24....空间的二进制表达长度最长24位
字符种数是3,用2位记录一个字符的权,log3(16000000)=15....空间的二进制表达长度最长30位
字符种数是5,用3位记录一个字符的权,log5(16000000)=10....空间的二进制表达长度最长30位
字符种数是9,用4位记录一个字符的权,log9(16000000)=7 ....空间的二进制表达长度最长28位
也就是说,最多要把bool开到flag[1024*1024*1024]这么大,但是....

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator