# 描述

Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.
Given a string s, we define a substring that happens exactly $k$ times as an important string, and you need to find out how many substrings which are important strings.

## Input

The first line contains an integer $T$ $(T≤100)$ implying the number of test cases.
For each test case, there are two lines:
the first line contains an integer $k$ $(k≥1)$ which is described above;
the second line contain a string s $(length(s)≤10^5)$.
It’s guaranteed that $∑length(s)≤2∗10^6$.

## Output

For each test case, print the number of the important substrings in a line.

# 思路

• 这类经典题目是在$height$数组上搞，所以我们先求原串的后缀数组。
• 将$height$数组每相邻$k-1$个一看，这个区间的最小值就是排名相邻的$k$个后缀的LCP，那么这个LCP必然出现了$k$次，那么这个LCP的前缀也必然出现了至少$k$次。问题在于解决这些串是不是严格出现了$k$次，只需要判断这些$height$值的前一个和后一个的$height$值，（记做$x,y$）那么长度为$1 \sim max(x,y)$的LCP的前缀出现了至少$k+1$次，因此要去掉这一部分（当然你直接按前面的方法求得出现至少$k+1$次再减去至少出现$k$次的也可以）。
• 但是还有一个坑点，就是如果$k=1$，$height$数组就不管用了，这个时候我们要把之前的RMQ求LCP变成$n-sa[i]$。
• 值得注意的是这里维护区间最小值不一定要用RMQ，可以用单调队列来维护。

0%