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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

波兰表  

2013-03-19 20:48:51|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
后来发现其实就是把倍增算法构造后缀数组的标号存下来。

在POI 2010 官方题解 P77面看到了这个东西。
由于不知道这个数据结构叫什么名字,波兰人原话是“这个数据结构”……有点"You-Know-Who"的感觉。
貌似是波兰人自己YY的,为了膜拜波兰人称之为波兰表好了!!

波兰表是一个很巧妙的避免字符串hash的方法!
波兰表解决的是这样的问题:每次给你两个区间[al, ar], [bl, br],问s[al, ar]和s[bl, br]这两个子串是否相等
波兰人给出了O(nlogn)预处理,O(1)在线回答的算法

布吉岛pair的同学可以先学习下C++的pair……懒得看的同学可以将pair理解成有序数对。

搞一个像ST表一样的数据结构
id[i, j]表示区间 [i, i + 2 ^ j)的一个id
我们要设计个字符串到整数的映射,使得当sa、sb为字符串时, id(sa) = id(sb) 等价于 sa = sb。
我们是采取hash函数来实现id的,这样只满足sa = sb时一定有id(sa) = id(sb),而反之不一定成立,所以hash是不安全的。

看似这个id不好设计?
但是我们发现,
[i, i + 2^j)是可以拆成两个串的:
[i, i + 2^(j - 1)), [i + 2^(j - 1), i + 2^j)
前一个的id是 id[i, j - 1],
后一个是id[i + 2^(j - 1), j - 1],
两个组成一个pair,就能唯一表示id[i, j]了。
难道说id[i, j]的数据类型是pair<int, int>?
不对啊,id[i, i + 2^(j - 1)]也是由下层的id来表示的啊!
那么id[i, j]的数据类型就是pair<<<...<int, int>, <int, int>>, <<int, int>, <int, int>>......>>>>了……
说了相当与没说……

关键的技巧在于,重标号!
我们按j从小到大的顺序计算id,j = 0时只有一个字符,那么id就是字符串对应位置的字符。
j > 0时,那么对于任意的i,id[i, j - 1]已经算出来了,且是整数类型。
对于所有i,将make_pair(id[i, j - 1], id[i + 2^(j - 1), j - 1])收集起来放到一个数组中,
然后排序,去重。
此时对应在数组中的位置就是我们要的新标号。
再枚举每个i,二分找到自己的pair对应的是几号,也就算出了id[i, j]。
注意到id最多只会到n,所以其实这几步是可以轻而易举使用基数排序优化到O(n)的。

那么考虑查询,s[al, ar] = s[bl, br]?
注意到两个区间的长度不一定是2的次幂。
所以还是仿照st表,多查询一段。如下图。
图中的W是我说的id。
只要查询左边一段和右边一段的id,组成一个pair,然后就可以直接比较两个pair来判断是否s[al, ar] = s[bl, br]了。
因为两个串的某个长度的前缀相等,某个长度的后缀相等,且这个前缀和这个后缀覆盖了整个串,那么这两个串就是相等的。
波兰表 - vfleaking - vfleaking的博客

(没看懂的可以回去补ST表。)

波兰人为啥要卡哈希?我想是为了让大家使用波兰表?(http://hi.baidu.com/sillycross/item/386b1e172389391fb98a1ab1)
波兰表以时间换正确性,真是给跪了!
好巧妙,波兰人就是不一样。

update:
纯洁的伪宅 中国脑筋 WJMZBMR神犇告诉我这其实就是后缀数组。一开始我还没反应过来……后来发现还真是这样。果然还是我太弱了呢……
(被鄙视了一脸:http://tieba.baidu.com/p/2220766142
波兰表就是把后缀数组的倍增法构造过程记录了下来。
算了还是叫波兰表了……
波兰表可以看做后缀数组的拓展?
这么一说起来,波兰表就好写多了,直接上后缀数组的模板,记录中间结果。
一个神奇的事情就是波兰人好像不知道后缀数组的样子,当我看见POI的后缀数组裸题时,波兰人总用各种神奇方法绕过去没用后缀数组。
提到波兰表的那一段在上面的图片中,大家擦亮眼睛……确实没看见后缀数组的波兰文对吧……波兰人很讲道理的,他凡是提到个什么甚至是dfs也会给你个链接告诉你哪有入门教程。
看来是波兰人自己YY出了类后缀数组数据结构。威武!
而用传统的后缀数组也是可捉的,求出height,然后用RMQ搞。
值得一提的是,RMQ是因为后缀数组的出现而被人研究的,因为后缀数组有个附赠品lcp数组。(我们常说的height数组)
值得一提的是,后缀数组有空间O(n),时间O(n)的构造算法,它就是众所周知的DC3算法。
值得一提的是,目前有RMQ在线的空间O(n),O(n)预处理,O(1)回答询问的算法。论文自称代码简洁。可以google下面的论文:
A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
值得一提的是,以上两个我仅仅只是知道名字,不知道算法是什么,当然也就没写过。
以上是想说,本文所述的问题实际上已经能用后缀数组在空间O(n),预处理时间O(n),询问时间O(1)解决。
从后缀数组的角度来理解波兰表貌似就是个比较显然的东西了,但是我还是觉得波兰表好神啊~
  评论这张
 
阅读(2129)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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