Cur1ed

后缀数组

ac自动机(12) cf(1) KMP&拓展KMP(22) 回文串(2) 图论(9) 字典树(6) 字符串(2) 未归档(87) 计算几何(1) 计算机网络实验(1) 题解(29)

/ 注册

全部文章 / 后缀数组（共21篇）

POJ - 3693 Maximum repetition substring（重复次数最多的连续重复子串）

传送门：POJ - 3693 题意：给你一个字符串，求重复次数最多的连续重复子串，如果有一样的，取字典序小的字符串。题解：比较容易理解的部分就是枚举长度为L，然后看长度为L的字符串最多连续出现几次。既然长度为L的串重复出现，那么str[0],str[l],str[2*l]……中肯定有两...

2020-04-04

0 878

POJ - 3693 Maximum repetition substring（重复次数最多的连续重复子串）

传送门：POJ - 3693 题意：给你一个字符串，求重复次数最多的连续重复子串，如果有一样的，取字典序小的字符串。题解：比较容易理解的部分就是枚举长度为L，然后看长度为L的字符串最多连续出现几次。既然长度为L的串重复出现，那么str[0],str[l],str[2*l]……中肯定有两...

2020-04-04

0 344

POJ - 2774 Long Long Message

传送门：POJ - 2774 （最长相同子串）题意：（在vj上看到了一个很有意思的描述）这个版本的 L学长喜欢上Z学妹，他发现他们的相似度很高，担心会不会就那么巧合，所以就想办法弄到了Z学妹的基因，然后也把自己的基因一起拿去比对，希望找出基因中完全一样的一段的最大长度，来判断要不要去德国骨科...

2020-04-03

0 392

POJ - 2774 Long Long Message

传送门：POJ - 2774 （最长相同子串）题意：（在vj上看到了一个很有意思的描述）这个版本的 L学长喜欢上Z学妹，他发现他们的相似度很高，担心会不会就那么巧合，所以就想办法弄到了Z学妹的基因，然后也把自己的基因一起拿去比对，希望找出基因中完全一样的一段的最大长度，来判断要不要去德国骨科...

2020-04-03

0 691

POJ - 2774 Long Long Message

传送门：POJ - 2774 （最长相同子串）题意：（在vj上看到了一个很有意思的描述）这个版本的 L学长喜欢上Z学妹，他发现他们的相似度很高，担心会不会就那么巧合，所以就想办法弄到了Z学妹的基因，然后也把自己的基因一起拿去比对，希望找出基因中完全一样的一段的最大长度，来判断要不要去德国骨科...

2020-04-03

0 393

POJ - 1743 Musical Theme （后缀数组）

题目链接：POJ - 1743 （不可重叠最长子串）题意：有N(1<=N<=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的子串，它需要满足如下条件： 1.长度至少为5个音符。 2.在乐曲中重复出现（就是出现过至少两次）。(可能...

2020-04-03

0 449

POJ - 1743 Musical Theme （后缀数组）

题目链接：POJ - 1743 （不可重叠最长子串）题意：有N(1<=N<=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的子串，它需要满足如下条件： 1.长度至少为5个音符。 2.在乐曲中重复出现（就是出现过至少两次）。(可能...

2020-04-03

0 548

POJ - 1743 Musical Theme （后缀数组）

题目链接：POJ - 1743 （不可重叠最长子串）题意：有N(1<=N<=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的子串，它需要满足如下条件： 1.长度至少为5个音符。 2.在乐曲中重复出现（就是出现过至少两次）。(可能...

2020-04-03

0 394

POJ - 2406 Power Strings （后缀数组DC3版）

题意：求最小循环节循环的次数。题解：这个题其实可以直接用kmp去求最小循环节，然后在用总长度除以循环节。但是因为在练后缀数组，所以写的后缀数组版本。用倍增***超时！！所以改用DC3法。对后缀数组还不是很理解，找了很多博客也没看懂到底有些数组到底记录的是啥，但他的实现过程很好理解，等我弄懂了再来...

2020-04-02

0 435

POJ - 2406 Power Strings （后缀数组DC3版）

题意：求最小循环节循环的次数。题解：这个题其实可以直接用kmp去求最小循环节，然后在用总长度除以循环节。但是因为在练后缀数组，所以写的后缀数组版本。用倍增***超时！！所以改用DC3法。对后缀数组还不是很理解，找了很多博客也没看懂到底有些数组到底记录的是啥，但他的实现过程很好理解，等我弄懂了再来...

2020-04-02

0 514