牛奶模式(后缀数组)

2017年11月20日270

牛奶模式

对问题的分析设计过程

题目要求序列中的最长的重复k次子序列,为一道经典的后缀数组+height数组例题

将序列求出其后缀数组即其h数组后,我们有$ans=max(RMQ(h[i],h[i+1],…,h[i+k]))$ 为了快速的进行上诉计算,可以考虑随着i的增大来维护一个数据结构,有下列两种方式:

  • 优先队列(堆)
  • 单调队列

程序中用到的数据机构和算法

本程序使用优先队列实现。

在初始化程序时使用离散化来避免初始时的桶排出现桶太大的情况。

程序的运行情况

一共提交了四次才通过,在提交时出现了下列问题:

  • 下标为1为0分不清楚
  • 在初始化时的离散化直接在s数组上修改出现问题

在实习过程中得到的经验和体会

  1. 在打程序时就要考虑到各种各样的边界问题
  2. 改变数组功能需要考虑是否会对后续操作出现冲突
  3. 后缀数组是解决字符串问题的一种利器

Code:

 

%d 博主赞过: