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

我实现的sa+rmq的版本

Posted by zengshiyuan at 2015-01-30 22:39:04 on Problem 3693
假设当前枚举的循环节长度为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:
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