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_map过了 不过为什么这个题也spj....

Posted by 20053565 at 2008-12-08 21:47:42 on Problem 3576
In Reply To:200题纪念,写个思路 Posted by:zfy0701 at 2008-07-30 14:40:27
> 主要是对树的hash,其实这题比3274 Gold Balanced Lineup还要容易,且时限放得更宽,建议对hash比较感兴趣的同学做此题,当然对于用map者,就更简单了。
> 
> 题目要求一个dfa,它满足两个条件,1、能识别所有词的dfa,2、要求状态数最少。
> 
> 其实,trie也可以看做是满足第一个条件的dfa,但是它不满足第二个条件
> 
> 这里设trans[i][x]表示状态i读取字符x所对应的转移。
> 我们设状态a有一颗子树为 t1(trans[a][i] = t1),b的一颗子树t2 (trans[b][j] = t2),如果t1和t2是一样的树,那么我们可以让 trans[a][i] = trans[b][j] = t1; 这样就节省了一颗子树的状态数。
> 
> 所以,我们可以在dfs的过程中对树进行hash和判重,不过完美hash不太可能做到。
> 
> 下面说说我的hash方案,设hashVaulue[i]表示状态i所代表的树的hash值,hash[x] 表示hash值x所对应的树,size为hash表大小。
> 
> 对于状态cur, p = sigma( hashValue[trans[cur][i]] * 26 + i) mod size (i=1..26, 且trans[cur][i]有对应转移。)
> 那么hashValue[cur] 就等于对 p进行线性探测所确定得值。
> 
> 这样hash方案是基于rabin-karp的,如果trie退化成一条链,就是非常明显的rabin-karp了。

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