Description

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:

Both S1 and S2 start and end with an alphabetic character

<li>Both S1 and S2 contain exactly k alphabetic characters</li> <li>For each alphabetic character c, the string S1 contains the same number of occurrences of c as the string S2. </li>

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.

输入数据 1 4 a'B'C'd'x'a'b'c'd 4 abcdabcd 0 输出数据 1 16 4

Source

CTU Open 2004

描述

一位不太出名的作家亚瑟・柯南・莫伊尔（Arthur Conan Moyle）终于发现了为什么他认为理应畅销的书籍却并不受欢迎。他注意到，由于频繁重复相同或相似的文本片段，他的作品变得有些乏味。他认为，提高书籍质量的最佳方法是直接舍弃首次重复出现之后的所有内容，这样一来，书籍便会有一种有趣的开放式结局的感觉。

起初，他试图寻找完全相同的文本片段，但这一方法失败了，因为重复的文本往往并非完全一致 —— 首次出现时为小写的字母，第二次出现时可能是大写，反之亦然；标点符号可能略有不同，甚至句子中的单词顺序也可能稍有差异。

为解决这些问题，他设计了以下更为复杂的重复片段识别标准（正整数 k 是该标准的一个参数，通过改变 k 的值，他可以控制多长的重复片段仍可被接受）：字母字符指的是 'a'-'z' 和 'A'-'Z' 这些字母。我们不区分字母的大小写，即 'a' 被视为与 'A' 相同的字母。

如果两个字符串 S1 和 S2 满足以下条件，则称它们在字母排列上是 k 相同的：

S1 和 S2 都以字母字符开头和结尾。

S1 和 S2 都恰好包含 k 个字母字符。

对于每个字母字符 c，字符串 S1 中 c 的出现次数与字符串 S2 中 c 的出现次数相同。

换句话说，如果字符串 S1 和 S2 在字母排列上是k相同的，那么它们包含的字母字符相同，但字母的排列顺序可能不同。你的任务是编写一个程序，从 ACM 的几本书籍中分离出最长的起始部分，该部分不包含在字母排列上是k相同的两个子字符串。

输入

输入包含多个实例。每个实例由两行描述。每个实例的第一行包含一个整数 1 ≤ k ≤ 50 1≤k≤50。第二行包含字符串 T，其长度最多为 100000 个字符。字符串 T 可能包含非字母字符（包括空格），但不包含任何具有特殊含义的字符（即 ASCII 码小于 32 的字符）。输入以包含数字 0 的一行结束。

输出

输出包含若干行。输出的第 i 行对应于输入的第 i 个实例。该行包含一个整数 —— 对应实例中字符串 T 的最长前缀 P 的长度（包括所有非字母字符），使得 P 不包含两个不同（但不一定不重叠）且在字母排列上是 k相同的子字符串 S1 和 S2。

输入数据 1

4

a'B'C'd'x'a'b'c'd

4

abcdabcd

0

输出数据 1

16

4

算法标签：

哈希表和哈希函数，滑动窗口；

题意分析

题目要求从输入字符串中分离出最长的起始部分，这部分满足条件：其中不存在两个子字符串在字母排列上是 k 相同的。所谓 k 相同 的定义是指两组字符集合完全一致，并且每个字符的数量差不超过 k。

此问题的核心在于判断任意两个子串是否满足上述条件并动态维护当前符合条件的最大前缀长度。

解题思路

利用哈希函数和滑动窗口思想来解决

滑动窗口技术：使用一个长度为k的窗口在字符串上滑动，统计窗口内字母的出现情况

规范化哈希：将窗口内的字母按字母表顺序排列生成哈希字符串，这样相同字母组成的子串会有相同的哈希值

哈希统计：使用哈希表统计每个规范化子串的出现次数，当某个子串出现第二次时，记录其位置

标程

#include <iostream>
#include <string>
#include <vector>
#include <map> // C++98 使用 map 替代 unordered_map
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cctype> // 用于 tolower
using namespace std;

const int maxn = 999997; // 定义哈希表的最大大小

int main() {
    srand(time(0)); // 初始化随机数种子
    
    // 初始化随机哈希系数（每个字母对应一个随机数）
    int sp[26];
    for (int i = 0; i < 26; i++) {
        sp[i] = rand() % (maxn - 100) + 90;
    }
    
    while (true) {
        int k;
        cin >> k; // 读取k值
        if (k == 0) break; // 输入0时退出程序
        cin.ignore(); // 忽略换行符
        
        string s;
        getline(cin, s); // 读取整行字符串
        
        int ans = s.length(); // 默认结果是整个字符串长度
        string t; // 用于存储处理后的纯字母字符串
        vector<int> map_pos; // 记录每个字母在原字符串中的位置
        
        // 处理输入字符串：
        // 1. 只保留字母字符
        // 2. 大写转为小写
        // 3. 记录每个保留字符在原串中的位置
        for (int i = 0; i < (int)s.length(); i++) { // C++98 使用 int 而非 size_t
            if ((s[i] >= 'A' && s[i] <= 'Z')) {
                t += tolower(s[i]); // C++98 兼容
                map_pos.push_back(i);
            } else if (s[i] >= 'a' && s[i] <= 'z') {
                t += s[i];
                map_pos.push_back(i);
            }
        }
        
        int n = t.length(); // 处理后的纯字母字符串长度
        if (n < k) { // 如果处理后的字符串比k短，直接输出原串长度
            cout << ans << endl;
            continue;
        }
        
        map<string, int> count_map; // C++98 使用 map 替代 unordered_map
        vector<int> con(26, 0); // 记录当前窗口中各字母的出现次数
        bool found = false; // 是否找到重复子串的标志
        
        // 初始化第一个窗口（前k-1个字符）
        for (int i = 0; i < k - 1; i++) {
            con[t[i] - 'a']++;
        }
        
        // 滑动窗口处理
        for (int i = k - 1; i < n; i++) {
            // 添加新字符到窗口
            con[t[i] - 'a']++;
            // 如果窗口已满，移除最左边的字符
            if (i >= k) {
                con[t[i - k] - 'a']--;
            }
            
            // 生成当前窗口的哈希字符串：
            // 将字母按顺序排列（如aabbbcc）
            string hash_str;
            for (char c = 'a'; c <= 'z'; c++) {
                for (int j = 0; j < con[c - 'a']; j++) {
                    hash_str += c;
                }
            }
            
            // 统计该哈希字符串出现的次数
            count_map[hash_str]++;
            // 如果出现次数达到2次，记录位置并退出循环
            if (count_map[hash_str] == 2) {
                ans = map_pos[i]; // 结果为该子串最后一个字符在原串中的位置
                found = true;
                break;
            }
        }
        
        cout << ans << endl; // 输出结果
    }
    return 0;
}