地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=6194
题目：
string string string
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 486 Accepted Submission(s): 125
Problem Description
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.
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)≤105).
It's guaranteed that ∑length(s)≤2∗106.
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)≤105).
It's guaranteed that ∑length(s)≤2∗106.
Output
For each test case, print the number of the important substrings in a line.
Sample Input
2
2
abcabc
3
abcabcabcabc
2
abcabc
3
abcabcabcabc
Sample Output
6
9
9
Source
思路：
sam会卡指针版的代码，不明白卡这么点内存有什么意思。
后缀自动机做法：建立sam后，统计出cnt数组，这一步要拓扑排序后倒着dp。
后缀数组做法：用f[i][j]表示height(i,j)的区间最小值，然后滑动大小为k的窗口，则贡献是max(0,f[i][j]-max(height[i-1],height[j+1]) )
后缀自动机做法：
#include <bits/stdc++.h> using namespace std; char ss[];
int ans; struct SAM
{
static const int MAXN = <<;//大小为字符串长度两倍
static const int LetterSize = ; int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];
int sum[MAXN], tp[MAXN], cnt[MAXN]; //sum,tp用于拓扑排序，tp为排序后的数组 void init( void)
{
last = tot = ;
len[] = ;
memset(ch,,sizeof ch);
memset(fa,,sizeof fa);
memset(cnt,,sizeof cnt);
} void add( int x)
{
int p = last, np = last = ++tot;
len[np] = len[p] + , cnt[last] = ;
while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
if( p == )
fa[np] = ;
else
{
int q = ch[p][x];
if( len[q] == len[p] + )
fa[np] = q;
else
{
int nq = ++tot;
memcpy( ch[nq], ch[q], sizeof ch[q]);
len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq;
while( p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
}
} void toposort( void)
{
for(int i = ; i <= len[last]; i++) sum[i] = ;
for(int i = ; i <= tot; i++) sum[len[i]]++;
for(int i = ; i <= len[last]; i++) sum[i] += sum[i-];
for(int i = ; i <= tot; i++) tp[sum[len[i]]--] = i;
}
} sam; int main(void)
{
//freopen("in.acm","r",stdin);
int t,k;cin>>t;
while(t--)
{
ans=;
sam.init();
scanf("%d%s",&k,ss);
for(int i=,len=strlen(ss);i<len;i++) sam.add(ss[i]-'a');
sam.toposort();
for(int i=sam.tot;i;i--)
{
int p=sam.tp[i],fp=sam.fa[p];
sam.cnt[fp]+=sam.cnt[p];
if(sam.cnt[p]==k)
ans+=sam.len[p]-sam.len[fp];
}
printf("%d\n",ans);
} return ;
}
后缀数组做法：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <iostream>
const int N = ;
int sa[N],s[N],wa[N], wb[N], ws[N], wv[N];
int rank[N], height[N];
char ss[N];
bool cmp(int r[], int a, int b, int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
} void da(int r[], int sa[], int n, int m)
{
int i, j, p, *x = wa, *y = wb;
for (i = ; i < m; ++i) ws[i] = ;
for (i = ; i < n; ++i) ws[x[i]=r[i]]++;
for (i = ; i < m; ++i) ws[i] += ws[i-];
for (i = n-; i >= ; --i) sa[--ws[x[i]]] = i;
for (j = , p = ; p < n; j *= , m = p)
{
for (p = , i = n - j; i < n; ++i) y[p++] = i;
for (i = ; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = ; i < n; ++i) wv[i] = x[y[i]];
for (i = ; i < m; ++i) ws[i] = ;
for (i = ; i < n; ++i) ws[wv[i]]++;
for (i = ; i < m; ++i) ws[i] += ws[i-];
for (i = n-; i >= ; --i) sa[--ws[wv[i]]] = y[i];
for (std::swap(x, y), p = , x[sa[]] = , i = ; i < n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
} void calheight(int r[], int sa[], int n)
{
int i, j, k = ;
for (i = ; i <= n; ++i) rank[sa[i]] = i;
for (i = ; i < n; height[rank[i++]] = k)
for (k?k--:, j = sa[rank[i]-]; r[i+k] == r[j+k]; k++);
}
struct RMQ
{
int log2[N],mi[N][];
void init(int n)
{
for(int i = ; i <= n; i ++)log2[i] = (i == ? - : log2[i >> ] + );
for(int j = ; j < log2[n]; j ++)
for(int i = ; i + ( << j) <= n + ; i ++)
mi[i][j] = std::min(mi[i][j - ], mi[i + ( << j - )][j - ]);
}
int query(int ql, int qr)
{
int k = log2[qr - ql + ];
return std::min(mi[ql][k], mi[qr - ( << k) + ][k]);
}
} rmq;
int sc(int i,int k,int len)
{
if(k==) return len-sa[i];
return rmq.query(i+,i+k-);
}
int main()
{
int t,k;std::cin>>t;
while(t--)
{
int ans=;
scanf("%d%s",&k,ss);
int len=strlen(ss);
for(int i=;i<len;i++)
s[i]=ss[i]-'a'+;
s[len]=;
da(s,sa,len+,);
calheight(s,sa,len);
height[len+]=;
for(int i=;i<=len;i++)
rmq.mi[i][]=height[i];
rmq.init(len);
for(int i=;i<=len-k+;i++)
ans+=std::max(sc(i,k,len)-std::max(height[i],height[i+k]),);
printf("%d\n",ans);
}
return ;
}