Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我实现的sa+rmq的版本假设当前枚举的循环节长度为l 相距为l的相邻两个下标为 j和j+l 直接暴力循环 从j枚举到j-l+1 枚举到当前的一个点假定是重复子串的起点s[k] 然后求s[k]后缀和s[k+l]后缀的lcp 用lcp/l+1去更新 k开头的最大重复子串数量(开一个数组记录 同时开多一个数组记录l值 方便输出) 假设s[k]!=s[k+l]了 提前退出循环 然后输出就是O(n)复杂度以内的事情了 按sa值从小到大枚举并维护最长重复子串的循环节数量 最后找到开头的位置 循环节长度l 和数量就很好输出了 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator