后缀数组

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

题目链接 题意：定义一个函数F．． For exampe: 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 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么）

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

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