题目链接

  题目问的是有多少个K连续重复子串，即连续出现K次的重复子串。

  思路：肯定是往后缀数组上想，但是中间出了点差错。

  错误一：在特判K==1的时候，应该是子串的数量，而不是文本串的长度，那么子串的数量就是。

  错误二：在我们枚举长度L的时候，算他们同时包含i和i + L的且连续出现次数大于等于K的时候的贡献，我算的贡献是前面往后有几种排列组合。但这是错误的，可以用整个的长度减去K*L再+1即可，因为我们可以在这段长度中任意滑动组成全长。

  错误三：我们的跳转，应该是跳转到最右边匹配到的位置的后面的位置，当然，为了保证复杂度，我们可以利用每次“+L”来看它是否会跳过去来保证其复杂度。

  总结了以上错误，然后才坎坎过了这题。

  讲一下完整的思路，首先，K连续会让我想到我们可以枚举长度，为了算贡献，我们或许会去把所有可以达到K连续的长度给存储下来，但这样的复杂度就是逆天了的，所以这里不能这样解，我们在算的过程中，就可以把答案得到了。于是乎，我们根据论文的思路，我们想知道i和i+L这两个点向左和向右的最长匹配（求LCP），也就是求height了。于是，我们不难算出最长连续匹配了，也就是包好i和i+L这两个点的最长（以L为循环节长度的）最长匹配长度了，然后我们可以将K*L左右滑动来记答案，所以这里的答案是总的长度减去K*L再加上1即可得到，然后统计全部答案即可。记得开long long。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 3e5 + 7;
struct SA
{int n, m;int s[maxN];int y[maxN], x[maxN], c[maxN], sa[maxN], rk[maxN], height[maxN];inline void get_SA(){for(int i=1; i<=m; i++) c[i] = 0;   //桶的初始化for(int i=1; i<=n; i++) ++c[x[i] = s[i]];for(int i=2; i<=m; i++) c[i] += c[i - 1];   //利用差分前缀和的思想知道每个关键字最多是在第几名for(int i=n; i>=1; i--) sa[c[x[i]]--] = i;for(int k=1; k<=n; k<<=1){int num = 0;for(int i=n - k + 1; i<=n; i++) y[++num] = i;for(int i=1; i<=n; i++) if(sa[i] > k) y[++num] = sa[i] - k; //是否可以作为第二关键字for(int i=1; i<=m; i++) c[i] = 0;for(int i=1; i<=n; i++) c[x[i]]++;  //因为上一次循环已经求出这次的第一关键字了for(int i=2; i<=m; i++) c[i] += c[i - 1];for(int i=n; i>=1; i--) //在同一第一关键字下，按第二关键字来排{sa[c[x[y[i]]]--] = y[i];y[i] = 0;}swap(x, y);x[sa[1]] = 1; num = 1;for(int i=2; i<=n; i++){x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;}if(num == n) break;m = num;}}inline void get_height(){int k = 0;for(int i=1; i<=n; i++) rk[sa[i]] = i;for(int i=1; i<=n; i++){if(rk[i] == 1) continue;    //第一名的height为0if(k) k--;  //height[i] >= height[i - 1] - 1int j = sa[rk[i] - 1];while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k++;height[rk[i]] = k;}}inline void clear(){n = 0; m = 200;}
} sa[2];
int LOG[maxN];
struct RMQ_struct
{int N;int dp_min[maxN][20];void RMQ(int id){for(int i=1; i<=N; i++) dp_min[i][0] = sa[id].height[i];for(int j=1; (1 << j) <= N; j++){for(int i=1; i + (1 << j) - 1 <= N; i++){dp_min[i][j]=min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);}}}int query(int l, int r){int i = LOG[r - l + 1];return min(dp_min[l][i], dp_min[r - (1 << i) + 1][i]);}
} rbt[2];
int N, K;
ll ans;
char s[maxN];
inline void sure_lenth()
{for(int L=1, k_len, l, r, k2_len, l2, r2, all_len; L <= N / K; L++) //枚举长度{int i = 1;while(i + L <= N){if(s[i] ^ s[i + L]) { i += L; continue; }l = sa[0].rk[i]; r = sa[0].rk[i + L];if(l > r) swap(l, r);l2 = sa[1].rk[N - (i + L) + 1]; r2 = sa[1].rk[N - (i) + 1];if(l2 > r2) swap(l2, r2);k_len = rbt[0].query(l + 1, r);k2_len = rbt[1].query(l2 + 1, r2);all_len = k_len + k2_len + L - 1;if(i + k_len - 1 + 1 < i + L - k2_len + 1) { i += L; continue; }if(all_len >= K * L){ans += all_len - K * L + 1;}int nex_pos = i + L + k_len;while(i < nex_pos) i += L;}}
}
int main()
{LOG[0] = 0; LOG[1] = 0;for(int i=1; (i << 1) < maxN; i <<= 1) LOG[i << 1] = LOG[i] + 1;for(int i=3; i < maxN; i++) LOG[i] = max(LOG[i], LOG[i - 1]);int T; scanf("%d", &T);while(T--){scanf("%d", &K);scanf("%s", s + 1);N = (int)strlen(s + 1);if(K == 1) { printf("%lld\n", 1LL * N * (N + 1) / 2); continue; }sa[0].clear(); sa[1].clear();for(int i=1; i<=N; i++) sa[0].s[++sa[0].n] = s[i];for(int i=N; i>=1; i--) sa[1].s[++sa[1].n] = s[i];sa[0].s[++sa[0].n] = 'a' + 26;sa[1].s[++sa[1].n] = 'a' + 26;sa[0].get_SA();sa[0].get_height();sa[1].get_SA();sa[1].get_height();rbt[0].N = N;rbt[0].RMQ(0);rbt[1].N = N;rbt[1].RMQ(1);ans = 0;sure_lenth();printf("%lld\n", ans);}return 0;
}