给定一个长度为n的字符串S和有一个数字a,统计长度大于等于a的出现次数最多的子串(不同的出现可以相交)，如果有多个,输出最长的，如果仍然有多个,输出第一次出现最早的。 编程要求:第一行输入数字a。第二行输入字符串S。笫3行输出结果

输入样例：
3
ababaababa
输出样例：
aba

【分析】

本题难度较大，需要使用字符串哈希或者后缀数组等高级算法。

以下为字符串哈希算法的讲解：

字符串哈希是一种用于字符串匹配的算法，它的基本思想是将字符串映射为一个固定长度的整数，从而实现字符串的快速匹配。

具体实现过程如下：

1. 首先定义一个基本的哈希函数，将字符串映射为一个整数，通常采用如下公式：

$$hash(s)=\sum_{i=0}^{n-1}s_i\times p^i$$

其中，$s$表示要哈希的字符串，$n$表示字符串的长度，$s_i$表示字符串中第$i$个字符的ASCII码值，$p$表示一个质数（通常取131或13331）。

2. 计算出每个子串的哈希值，用一个数组$H$来存储。具体实现如下：

$$H[i]=\sum_{j=0}^{len-1}s_{i+j}\times p^j$$

其中，$len$表示子串的长度。

3. 对于每个长度为$a$的子串，统计其出现次数。具体实现如下：

对于$len\geq a$的子串，对应的哈希值为$H[i]$，统计其出现次数需要遍历整个哈希数组，时间复杂度为$O(n)$。

4. 找到出现次数最多的子串。具体实现如下：

遍历哈希数组，找到出现次数最多的子串，并记录其长度和出现位置。如果出现次数相同，选择长度最长的子串，如果长度也相同，则选择出现位置最早的子串。时间复杂度为$O(n)$。

【代码】

相关问题

C语言：给定一个长度为n的字符串S和有一个数字a，统计长度大于等于a的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。编程要求：第一行输入数字a。 第二行输入字符串S。第三行输出结果

输入样例：
3
abcbcbcbcd
输出样例：
3
bcbc

解题思路：
1. 遍历所有长度大于等于a的子串，存储在一个字符串数组中。
2. 对字符串数组进行排序，按照出现次数从大到小排序，如果出现次数相同，则按照长度从大到小排序，如果长度也相同，则按照第一次出现的位置从小到大排序。
3. 输出排完序后的第一个元素，即为出现次数最多且长度最长、第一次出现最早的子串。

AC代码：

使用C语言编码：给定一个长度为n的字符串S和有一个数字a，统计长度大于等于a的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。编程要求：第一行输入数字a。 第二行输入字符串S。第三行输出结果

示例输入：

3
abcabcabcabc
示例输出：

abc
解释：长度大于等于3的子串有abc, bca, cab, abc, bca, cab, abc, bca, cab, abc, abc, bca, cab, abc, abc, abc, bca, cab, abc, abc, abc, abc, bca, cab, abc。其中abc出现次数最多，且是最长的，输出abc。