题意在题面里面应该说得足够清楚了，这里不再重复。题面里面有一个条件是纯粹唬人的：“长度不小于l”。显然地，只要存在一个长度大于l的解，那么就一定存在一个长度等于l的解。所以，只要考虑等于l的情况就行了。

来到这里，就需要作一点分析，决定算法的核心思想。在这里得到的结果不同，最终解答就会不同。我没有很深地挖掘可选的解决策略，在我所能想到直接联想到的算法里面，基本上都是建立在以下两种东西上：一是原串的子串，二是原串的后缀。

首先来分析基于子串的算法。这些算法使用一种直观的思想：枚举可能的子串，然后与原串进行串匹配，在所有解中找到最优的。串匹配有很多算法，包括著名的Knuth-Morris-Pratt、稍微不那么著名的Boyer-Moore，还有基于自动机的算法。其中KMP以及BM的一个变种的最坏情况时间复杂度是线性的。利用这两个算法，就可以将整个算法的时间复杂度做到O(n^2)，其中n是s的长度。在这个之上，还可以进一步做事情。譬如在枚举这一步，可以通过一些办法提取出子串的一些特征，减少需要匹配的子串数目，削减匹配的强度。

其次来分析基于后缀的算法。不难观察到每个子串都是原串的一个后缀的前缀。如果可以把原串的所有后缀根据它们的前缀组织起来，那么也就可以将问题解决了。有两种成熟的数据结构分别实现了这个思想：后缀数组（Suffix Array）和后缀树（Suffix Tree）。简单地说，后缀数组即是一个存放了将一个串的所有后缀按字典序排序后的结果的数组，后缀树则是一个保存了一个串的所有后缀的Trie。从目前已有的构造算法复杂程度的角度来看，后缀数组比后缀数更简单些。我做的解答正是基于后缀数组的。

我想花一点点笔墨来简单解释一下我的参考解答。整个算法分成三部分：1.构造后缀数组；2.计算后缀数组中相邻后缀的最长公共前缀（Longest Common Prefix）；3.利用最长公共前缀信息求解问题。下面举一个具体的例子。设s = "ababa"，那么它的所有后缀就是：

ababa baba aba ba a

把它们按照字典序排序之后就是

a aba ababa ba baba

它们原串中出现的位置分别是

4 2 0 3 1

在这个顺序里从上到下相邻的两个后缀的最长公共前缀分别是

a aba （空串） ba

它们的长度和关联的后缀（用在原串中的出现位置表示）分别是

  1   3   0   2
 / \ / \ / \ / \
4   2   0   3   1

在这个图里面，具有相同前缀的后缀一定是相邻的，而且它们的最长公共前缀的长度决定于两两相邻的最长公共前缀中最短的一个。譬如a、aba、ababa三个后缀，它们都包含最长公共前缀a。它们在原串出现的位置分别是4、2、0，最长公共前缀的长度1正是上图中1和3的小者。

可见，如果可以快速地得到上面这些信息，那么就可以得到问题的高效算法。实际上，，构造后缀数组和计算最长公共前缀都有O(n)时间的算法（需要假设串的字母表的大小是O(n)的，因为算法涉及基数排序）。解决问题的第3步也可以在O(n)时间内完成（同样需要前面的假设）。因此，这个问题是可以在O(n)时间内解决的。

不过我的解答不是O(n)而是O(nlogn)的。额外的这个logn因子来自于构造后缀数组一步，我用的是一个O(nlogn)的算法，它比O(n)的算法要简单、清晰些。

--------------------------------------------------

以下部分为程序测试分析和结果。

程序测试使用的数据是Fibonacci串。Fibonacci串的定义类似于Fibonacci数列：F_1 = "b", F_2 = "a", F_n = F_n-1 * F_n-2，其中“*”表示串连接。Fibonacci串的定义使得它具有很多的重复字串，因此对它进行压缩的时候具有很高的压缩比。测试中使用的共1446K的数据经过RAR压缩后只剩下5.7K，压缩比达到253。

数据分成7组。s的分别是第一个长度不小于1、10、100、1000、10000、100000、1000000的Fibonacci串。l的数值则为s的长度的1%到10%之间的一个随机值。

测试结果如下（时间单位为毫秒，内存单位为K）：

             Test 1 Test 2 Test 3 Test 4 Test 5 Test 6 Test 7
Time Limit   5000   5000   5000   5000   10000  10000  30000
Memory Limit 30000  30000  30000  30000  300000 300000 300000

Name         
csea         NO     0      0      3718   NO     NO     N/A
luoyanxia    15     0      0      NO     NO     NO     N/A
maths_dxj    0      0      0      0      78     4828   NO
ccpplus      0      0      93     NO     NO     NO     N/A
latalata     0      0      0      0      468    NO     NO
zhaoyg       0      0      234    NO     NO     NO     N/A
烈焰燃烧     0      NO     NO     NO     NO     NO     N/A
zheni        0      0      0      NO     NO     NO     N/A
david2211    NO     NO     NO     NO     NO     NO     N/A
hj36277      0      0      0      406    NO     NO     N/A
小黑骑DK     0      0      0      0      265    5468   NO
liyanguestc  0      NO     NO     NO     NO     NO     N/A
aloe         0      NO     NO     NO     NO     NO     N/A
liangvictor  0      0      781    NO     NO     NO     N/A
goal00001111 0      0      0      31     1000   NO     NO
fjqqj        0      0      0      62     NO     NO     N/A
yxs0001      0      0      0      NO     NO     NO     N/A
crossbow     0      0      0      0      15     562    11984

根据这个结果，优胜者肯定在maths_dxj和小黑骑DK之间决定。不过我还是想简单说一下一些解答的情况。

csea的解答是第一个，也颇具代表性，算法就是枚举加朴素匹配，时间复杂度是O(n^3)。这一点在第4组数据体现得很明显，虽然数据的规模是千的量级，但是程序运行的时间已经达数秒。latalata的解答中有些写法比较奇怪，char*是可以直接加上一个整数，不需要用循环和++。zheni、liyanguestc、goal00001111都用到了KMP，但似乎只有goal00001111用好了KMP，其他二人的程序都有些问题，KMP应该是能撑到第5组数据的。yxs0001的解答很有趣，算法不断维护一个Trie，Trie中保存了以当前字符为结尾、长度不超过l的后缀，但是实现似乎有错。

maths_dxj和小黑骑DK用的算法都是基于朴素的串匹配的算法。两个人各自做了两个不同的优化。如goal00001111在另帖中分析，maths_dxj标记了匹配出现的位置，避免重复子串的处理。小黑骑DK则是根据当前解的情况估算了串匹配位置的界，在无望得到更优解的时候提早停止匹配。小黑骑DK的优化还可以做得更彻底些，在第二层循环里也加上一个界的估算，这时第6组的时间可以降到687毫秒。这两个优化也可以同时做，但是效果似乎不明显。

第7组数据只测了通过了第5组数据的程序，但是没有程序能在可以接受的时间内跑出结果来。

测试时对部分程序进行了修改使之能够避免一些可能出现的问题。测试得到的运行时间可能有60毫秒以内的误差。

maths_dxj和小黑骑DK的算法谁比谁好不容易，具体测试得到的运行时间也受制于数据的特性，所以决定maths_dxj和小黑骑DK共同优胜。