分析

不会后缀数组实锤了。考虑求 还可以使用字符串哈希。二分 哈希，时间复杂度也是 。代码也挺短的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 1e5 + 100,D = 233;
ull f[N],g[N],p[N];
int n,m;
char s[N],t[N];
ull ask(ull *a,int l,int r) {
    return a[r] - a[l - 1] * p[r - l + 1];
}
int lcp(int x,int y,int r) {
    int l = 1,t = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(ask(f,x,x + mid - 1) == ask(g,y,y + mid - 1)) {
            t = mid;l = mid + 1;
        }
        else r = mid - 1;
    }
    return t;
}
bool check(int x) {
    int r = x + m - 1,y = 1;
    for(int i = 0;i < 3;i++) {
        int t = lcp(x,y,m-y+1);
        x += t + 1;y += t + 1;
        if(y > m) return 1;
    }
    return ask(f,x,r) == ask(g,y,m);
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        scanf("%s%s",s + 1,t + 1);
        n = strlen(s + 1);m = strlen(t + 1);
        if(n < m) {printf("0\n");continue;}
        p[0] = 1;
        for(int i = 1;i <= n;i++) p[i] = p[i - 1] * D;
        for(int i = 1;i <= n;i++) f[i] = f[i - 1] * D + s[i];
        for(int i = 1;i <= m;i++) g[i] = g[i - 1] * D + t[i];
        int ans = 0;
        for(int i = 1;i + m - 1 <= n;i++) {
            if(check(i)) ans++;
        }
        printf("%d\n",ans);
    }
}