转自：

题意：

告诉你一个字符串和k ， 求这个字符串中有多少不同的子串恰好出现了k 次。

思路：

后缀数组。

我们先考虑至少出现k 次的子串， 所以我们枚举排好序的后缀i (sa[i]) 。

k段k 段的枚举。

假设当前枚举的是 sa[i]~sa[i + k -1]

那么假设这一段的最长公共前缀  是L 的话。

那么就有L 个不同的子串至少出现了k次。

我们要减去至少出现k + 1次的 ， 但还要和这个k 段的lcp 有关系， 因此肯定就是 这一段 向上找一个后缀 或者向下找一个后缀。

即  sa[i-1] ~ sa[i + k - 1]  和 sa[i] ~ sa[i + k] 求两次lcp 减去即可。

但是会减多了。

减多的显然是sa[i-1] ~ sa[i + k] 的lcp。 加上即可。

注意 k =1的情况在求lcp 会有 问题， 即求一个串的最长公共前缀会有问题， 特判一下即可。

一定要注意边界问题 边界问题 边界问题！！！

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5   6 const int maxn = 100000 + 10;  7   8 int t1[maxn], t2[maxn], c[maxn];  9  10 bool cmp(int* r, int a,int b,int l){ 11     return r[a] == r[b] && r[a+l] == r[b+l]; 12 } 13  14 void da(int str[], int sa[], int Rank[], int lcp[], int n, int m){ 15     ++n; 16     int i, j, p, *x = t1, *y = t2; 17     for (i = 0; i < m; ++i) c[i] = 0; 18 //        puts("hha"); 19     for (i = 0; i < n; ++i) c[x[i] = str[i] ]++; 20     for (i = 1; i < m; ++i) c[i] += c[i-1]; 21     for (i = n-1; i >= 0; --i) sa[--c[x[i] ] ] = i; 22     for (j = 1; j <= n; j <<= 1){ 23         p = 0; 24         for (i = n-j; i < n; ++i) y[p++] = i; 25         for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 26         for (i = 0; i < m; ++i) c[i] = 0; 27         for (i = 0; i < n; ++i) c[x[y[i] ] ]++; 28  29         for (i = 1; i < m; ++i) c[i] += c[i-1]; 30         for (i = n-1; i >= 0; --i) sa[--c[x[y[i] ] ] ] = y[i]; 31  32         swap(x,y); 33         p = 1; x[sa[0] ] = 0; 34         for (i = 1; i < n; ++i){ 35             x[sa[i] ] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; 36  37  38         } 39  40         if (p >= n)break; 41         m= p; 42  43  44     } 45  46     int k = 0; 47     n--; 48     for (i = 0; i <= n; ++i) Rank[sa[i] ] = i; 49     for (i = 0; i < n; ++i){ 50         if (k)--k; 51         j = sa[Rank[i]-1 ]; 52         while(str[i+k] == str[j+k])++k; 53         lcp[Rank[i] ] = k; 54     } 55 } 56  57 int lcp[maxn], a[maxn], sa[maxn], Rank[maxn]; 58  59 char s[maxn]; 60  61 int d[maxn][40]; 62 int len; 63  64 void rmq_init(int* A, int n){ 65     for (int i = 0; i < n; ++i) d[i][0] = A[i]; 66     for (int j = 1; (1<
        
         <= n; ++j) 67         for (int i = 0; i + (1<
         
           0)ans -= ask(i - 1, i + k - 1); ///注意边界问题。102             if (i + k <= len)ans -= ask(i, i + k);103             if (i - 1 > 0 && i + k <= len)ans += ask(i - 1 , i + k);104         }105         printf("%I64d\n", ans);106 107 108     }109     return 0;110 }111