题目链接【http://acm.hdu.edu.cn/showproblem.php?pid=6194】
题意：
给你一个长度不大于1e5的字符串，然后然你判断其子串严格出现k次的子串个数。
题解：
后缀数组 + RMQ。首先说一下后缀数组里面的三个数组的作用：
sa[i] 数组 : 排名为i的后缀是[sa[i] - end];
Rank[i] 数组 : 后缀为[i - end]的排名是Rank[i]
height[i] 数组 : 排名为i的后缀和排名为i - 1的后缀的最长前缀。
这里主要用到了height数组，首先我们考虑k == 1的情况，tmp = max(height[i], height[i + 1]),tmp表示排名为i的串和排名为i-1的串的公共前缀及排名为i+1的串和排名为i的串的公共前缀的最大值，那么可以知道排名为i的串中一共有len[i](排名为i的串的长度) - tmp个。
当k>1的时候，我们就要维护height的区间最小值了。从排名为k的串开始枚举（排名在k之前的串肯定出现不了k次），我们维护
int tmp = RMQMI(i - lenk + 2, i);
int x = max(height[i + 1], height[i - lenk + 1]);
if(tmp - x > 0) ans += tmp - x;
tmp,表示串i-lenk+1,到串i的公共不部分，表示公共部分的串出现了k次或者以上，再判断max(height[i + 1], height[i - lenk + 1]);，答案即为 tmp - x。
#include<bits/stdc++.h>
const int maxn = 1e6 + 5;
using namespace std;
char s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
int T, lenk;
void build_sa(int m)
{
int *x = t, *y = t2;
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
for(int i = 1; i < m; i++) c[i] += c[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
for(int k = 1; k <= n; k <<= 1)
{
int p = 0;
for(int i = n - k; i < n; i++) y[p++] = i;
for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(int i = 0; i < m; i++) c[i] = 0;
for(int i = 0; i < n; i++) c[x[y[i]]]++;
for(int i = 0; i < m; i++) c[i] += c[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for(int i = 1; i < n; i++)
x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
if(p >= n) break;
m = p;
}
}
int cmp_suffix(char* pattern, int p, int m)
{
return strncmp(pattern, s + sa[p], m);
}
int Rank[maxn], height[maxn];
void getHeight()
{
int i, j, k = 0;
for(i = 0; i < n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[Rank[i]] = k;
}
height[0] = 0;
}
int mi[maxn][20], lmt[maxn];
void InitRMQ()
{
int N = n - 1;
lmt[0] = -1;
for(int i = 1; i <= N; i++)
{
lmt[i] = ((i & (i - 1)) == 0) ? lmt[i - 1] + 1 : lmt[i - 1];
mi[i][0] = height[i];
}
for(int j = 1; j <= lmt[N]; j++)
{
for(int i = 1; i + (1 << j) - 1 <= N; i++)
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
}
}
int RMQMI(int x, int y)
{
int k = lmt[y - x + 1];
return min(mi[x][k], mi[y - (1 << k) + 1][k]);
}
int main ()
{
scanf("%d", &T);
while(T--)
{
scanf("%d %s", &lenk, s);
n = strlen(s) + 1;
build_sa(127);
for(int i = 1; i <= n; i++) height[i] = 0;
getHeight();
int ans = 0;
if(lenk == 1)
{
for(int i = 1; i < n; i++)
{
int len = n - sa[i] - 1;
int tmp = max(height[i], height[i + 1]);
if(len - tmp > 0) ans += len - tmp;
}
}
else
{
InitRMQ();
for(int i = lenk; i < n; i++)
{
int tmp = RMQMI(i - lenk + 2, i);
int x = max(height[i + 1], height[i - lenk + 1]);
if(tmp - x > 0) ans += tmp - x;
}
}
printf("%d\n", ans);
}
return 0;
}