考虑到K很小，于是可以暴搜每次用的是哪种操作，跳过AB相等的字符可以用SA求LCP加速。

主要流程就是，枚举B的每个后缀，对每个后缀统计合法前缀个数。DFS搜索每次决策，用SA跳过相同字符，当A或B匹配到结尾时统计答案。

每次某个串匹配到结尾时，B中的某个区间的前缀都会合法，注意到这些合法的前缀长度与A长度相差一定不超过K，于是用一个2*K+1的差分数组记录答案即可。复杂度$O(n\log n+n3^K)$

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 using namespace std; 6  7 const int N=200010; 8 int K,m,na,nb,n,d,ans,lg[N],h[N],c[N],x[N],y[N],sa[N],rk[N],st[N][20]; 9 char s[N],A[N],B[N];10 11 bool Cmp(int a,int b,int l){ return y[a]==y[b] && y[a+l]==y[b+l]; }12 13 void getSA(int m){14     memset(y,0,sizeof(y));15     rep(i,0,m) c[i]=0;16     rep(i,1,n) c[x[i]=s[i]]++;17     rep(i,1,m) c[i]+=c[i-1];18     for (int i=n; i; i--) sa[c[x[i]]--]=i;19     for (int k=1,p=0; p
        
         k) y[++p]=sa[i]-k;22         rep(i,0,m) c[i]=0;23         rep(i,1,n) c[x[y[i]]]++;24         rep(i,1,m) c[i]+=c[i-1];25         for (int i=n; i; i--) sa[c[x[y[i]]]--]=y[i];26         rep(i,0,n) y[i]=x[i]; p=1; x[sa[1]]=1;27         rep(i,2,n) x[sa[i]]=Cmp(sa[i],sa[i-1],k)?p:++p;28     }29 }30 31 void getH(){32     rep(i,1,n) rk[sa[i]]=i; int k=0;33     rep(i,1,n){34         for (int j=sa[rk[i]-1]; j+k<=n && i+k<=n && s[i+k]==s[j+k]; k++);35         h[rk[i]]=k; if (k) k--;36     }37 }38 39 void init(){40     lg[1]=0; rep(i,2,n) lg[i]=lg[i>>1]+1;41     rep(i,1,n) st[i][0]=h[i];42     rep(i,1,19) rep(j,1,n-(1<
         
          y) swap(x,y);48     x++; int t=lg[y-x+1];49     return min(st[x][t],st[y-(1<
          
           na || y>nb){57 int c=K-z-(na-x+1);58 if (c>=0) col(y-1-c,y-1+c);59 return;60 }61 if (z==K) return;62 dfs(x+1,y,z+1); dfs(x,y+1,z+1); dfs(x+1,y+1,z+1);63 }64 65 int main(){66 freopen("bzoj4340.in","r",stdin);67 freopen("bzoj4340.out","w",stdout);68 scanf("%d%s%s",&K,A+1,B+1); m=2*K+1;69 na=strlen(A+1); nb=strlen(B+1);70 rep(i,1,na) s[++n]=A[i]; s[++n]='#';71 rep(i,1,nb) s[++n]=B[i];72 getSA(300); getH(); init();73 for (d=1; d<=nb; d++){74 rep(j,1,m) c[j]=0;75 dfs(1,d,0);76 rep(j,1,m){77 c[j]+=c[j-1];78 if (c[j]) ans++;79 }80 }81 printf("%d\n",ans);82 return 0;83 }