编程介的小学生 2017-02-16 13:34 采纳率: 20.5%
浏览 757
已采纳

God of the Vile Baskers

A not very famous writer Arthur Conan Moyle has finally found out why his books are not as popular as he believes they would deserve. He noticed that his works are getting a bit boring due to frequent repetitions of same or similar pieces of text. He decided that the best way how to improve the quality of his books is to simply throw away everything after the first repetition - the books then get an interesting open-ended feeling.

First he attempted to look for exactly same pieces of text, but this failed, since the repeated texts often do not match precisely - some of letters that are lowercase in the first place may be uppercase in the second and vice versa, punctuation may be a bit different, and even the words in sentences may be in slightly different order. To overcome these problems, he devised the following more involved criterion for recognizing duplicates (a positive integer k is a parameter of his criterion; by changing it he affects how long repeated pieces are still acceptable):

Alphabetic characters are the letters 'a'-'z' and 'A'-'Z'. We do not distinguish case of the letters, i.e. 'a' is supposed to be the same letter as 'A'.

Two strings S1 and S2 are k-identical up to permutation of letters if:

  1. Both S1 and S2 start and end with an alphabetic character
  2. Both S1 and S2 contain exactly k alphabetic characters
  3. For each alphabetic character c, the string S1 contains the same number of occurrences of c as the string S2.

In other words, if the strings S1 and S2 are k-identical up to permutation of letters, then the alphabetic characters in them are the same, but their ordering may be different.

Your task is to write a program that separates a longest initial part that does not contain two substrings k-identical up to permutation of letters from several of the ACM's books.

Input

The input consists of several instances. Each instance is described by two lines.

The first line of the instance consists of an integer number 1 <= k <= 50. The second line of the instance consists of the string T. Length of T is at most 100 000 characters. The string T may contain non-alphabetic characters including spaces, but it does not contain any characters with special meaning (i.e. with ASCII code smaller than 32).

The input is terminated by a line containing a zero.

Output

The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. The line a single integer number - length of the longest prefix P (including all non-alphabetic characters) of the string T of the corresponding instance such that P does not contain two distinct, but not necessarily non-overlapping, substrings S1 and S2 that are k-identical up to permutation of letters.

Sample Input

4
a'B'C'd'x'a'b'c'd
4
abcdabcd
0
Sample Output

16
4

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-21 15:17
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能