后缀数组

题目链接 题意：把一个长度为 n 的只由数字构成的串分成 k 个不为空的子串，使得最大的串最小（大小是指串所对应的十进制数的大小）。

题目链接 题意：定义一个函数 F。 For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12)

poj 2406 题意：给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值

题目连接 题意：求所有不同的子串个数。 思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串。假设字符串的长度为 n，那么长度为 1 的子串有 n 个，为 2 的有 n-1 个……为 n 的有 1 个，一共就是 n*(n+1)/2 个，但是实际上会有重复的。

poj3261 题意：给一个字符串，要求找出至少出现k次的最长重复子串…

poj 1743 题意：n 个数字（1..88）表示的音符，问最长的连续两段长度至少为 5 的变化相同的音符段的长度。

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么）

poj 2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。

原文链接：链接 讲了后缀数组的概念，然后从最暴力的 O(nnlogn) 的复杂度（O(n) 用来比较字符串，O(nlogn) 是排序的复杂度）逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇 The Skew Algorithm 的论文。