思路：通过学习后缀数组知识了解，第i大的后缀和第j大的后缀的lcp等于它们之间，所有相邻对的lcp的最小值。然后题意是最多可以skip3个不同的点，求 s s s中有多少子串和 s 0 s_0 s0匹配。
const int N = 2e5+5, M = 21; char s[N],s0[N]; int sa[N], t[N << 1], t2[N << 1], c[N], height[N], rk[N]; int n, m; void get_sa() { //s从1开始，排名从1开始 int i, *x = t, *y = t2, m = 256; for (i = 1;i <= m;i++)c[i] = 0; for (i = 1;i <= n;i++)c[x[i] = s[i]]++; for (int i = 2;i <= m;i++)c[i] += c[i - 1]; for (i = n;i;i--)sa[c[x[i]]--] = i; for (int k = 1;k <= n;k <<= 1) { int num = 0; for (i = n - k + 1;i <= n;i++)y[++num] = i; for (i = 1;i <= n;i++)if (sa[i] > k)y[++num] = sa[i] - k; for (i = 1;i <= m;i++)c[i] = 0; for (i = 1;i <= n;i++)c[x[i]]++; for (i = 2;i <= m;i++)c[i] += c[i - 1]; for (i = n;i;i--)sa[c[x[y[i]]]--] = y[i]; 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; } } 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; if (k)k--; int j = sa[rk[i] - 1]; while (j + k <= n && i + k <= n && s[i + k] == s[j + k])k++; height[rk[i]] = k; } } int rmq[N][M + 2], Lg2[N]; void get_st() { for (int i = 1;i <= n;i++) rmq[i][0] = height[i]; for (int i = 2;i <= n;i++) Lg2[i] = Lg2[i >> 1] + 1; for (int k = 1;(1 << k) <= n;k++) for (int i = 1;i + (1 << k) - 1 <= n;i++) rmq[i][k] = min(rmq[i][k - 1], rmq[i + (1 << k - 1)][k - 1]); } int lcp(int x, int y) { int i = rk[x], j = rk[y]; if (i > j) swap(i, j); int t = Lg2[j - i]; return min(rmq[i + 1][t], rmq[j - (1 << t) + 1][t]); } int main() { //freopen("in.txt", "r", stdin); int t;t = in(); while (t--) { scanf("%s%s", s + 1, s0 + 1); int lens = strlen(s + 1), lens0 = strlen(s0 + 1); n = lens + lens0;//两个串接起来，后序求lcp f(i, 1, lens0)s[i+lens] = s0[i]; get_sa(); get_height(); get_st(); int re = lens - lens0; if (re < 0) { puts("0");continue; } int ans = 0; f(i, 1, 1 + re) { int num = 0; int len = 0;//lcp长度 while (num <=3 && len <= lens0) { int nowlcp = lcp(i+len, lens + 1 + len); len += nowlcp+(num<3); num++; } if (len >=lens0)ans++; } cout << ans << endl; } return 0; }