STAMMER - Stammering Aliens

### 题目描述 $Dr. Ellie$ $Arroway$博士已经和外星文明建立了一些联系。不过，但目前为止，他们所有解密的努力全失败了。但幸运的是，他们偶然的发现了一群有些口吃的外星人。她的团队发现，在一串足够长的信息中，一些最重要的信息会以连续的字符重复出现多次，甚至可能夹杂在其他单词中。而且，这群外星人有时会把一些单词进行缩写，但博士的团队看起来，有些模棱两可。例如，如果外星人需要说两边$bab$，他们也许会以$babab$的形式发出消息。这是一种缩写，因为第一遍$bab$中的第二个$b$可以和第二遍中的第一个$b$连在一起重复使用。 正因如此，这些消息可能会包含一些多次重复的单词。因此，$Ellie$向你--$S.R. Hadden$求助，来帮助提取这些消息中的重要信息。 现在给你一个整数$m$和一串代表外星人的消息，要求你去找到一个至少出现$m$次的最长字符串$s$。例如，在一串消息$baaaababababbababbab$中，长度为5的字符串$babab$出现了$3$次,即在该串的$5$、$7$和$12$个字符上(字符计数从$0$开始)。而另外出现大于等于$3$次的字符串都没有比这个更长了（见$input$的第一组数据）。对于第二组数据，没有子串出现$11$次或更多次的了。 若一个字符串有多解，则我们选择最右边的一个。 ------------ ### 输入描述 输入包含多组数据。每组数据共两行，都由一个$m(m \ge 1)$和一个长度小于$40000$的字符串组成。字符串中的所有字符都是从$a$到$z$的小写字母。最后以$m = 0$作为输入的结束，不算在输入的数据中。 ------------ ### 输出描述 对于每组数据，输出两个整数，之间由一个空格隔开，分别表示至少出现$m$次的字符串的最大长度和这个子串最右边可能的开始的位置。**若无解，则输出$none$！** ------------ ### 样例输入 ``` 3 baaaababababbababbab 11 baaaababababbababbab 3 cccccc 0 ``` ------------ ### 样例输出 ``` 5 12 none 4 2 ```

Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found out that, in every long enough message, the most important words appear repeated a certain number of times as a sequence of consecutive characters, even in the middle of other words. Furthermore, sometimes they use contractions in an obscure manner. For example, if they need to say _bab_ twice, they might just send the message _babab_, which has been abbreviated because the second _b_ of the first word can be reused as the first _b_ of the second one. Thus, the message contains possibly overlapping repetitions of the same words over and over again. As a result, Ellie turns to you, S.R. Hadden, for help in identifying the gist of the message. Given an integer _m_, and a string _s_, representing the message, your task is to find the longest substring of _s_ that appears at least _m_ times. For example, in the message _baaaababababbababbab_, the length-5 word _babab_ is contained 3 times, namely at positions 5, 7 and 12 (where indices start at zero). No substring appearing 3 or more times is longer (see the first example from the sample input). On the other hand, no substring appears 11 times or more (see example 2). In case there are several solutions, the substring with the rightmost occurrence is preferred (see example 3). **Input** The input contains several test cases. Each test case consists of a line with an integer _m_ (_m_ >= 1), the minimum number of repetitions, followed by a line containing a string _s_ of length between _m_ and 40 000, inclusive. All characters in _s_ are lowercase characters from “a” to “z”. The last test case is denoted by _m_ = 0 and must not be processed. **Output** Print one line of output for each test case. If there is no solution, output none; otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least _m_ times; the second integer gives the rightmost possible starting position of such a substring. **Sample Input** ``` <pre class="verbatim">3 baaaababababbababbab 11 baaaababababbababbab 3 cccccc 0 ```