Description

给定两个串A，B。请问B中有多少个非空子串和A的编辑距离不超过K？

所谓“子串”，指的是B中连续的一段。不同位置的内容相同的子串算作多个。

两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的操作次数，

每次操作可以插入、删除或者替换一个字符。

Input

第一行一个非负整数K。接下来两行，每行一个由大写字母组成的字符串，分别表示A和B。

Output

输出一行一个整数，表示所求答案。

Sample Input

1

AAA

AABBAAB

Sample Output

5

HINT

对100%的数据，K≤5，两个字符串均非空，长度和小于10^5.

Solution

先把字符串拼起来建个后缀数组。

看到$k$不大，考虑枚举左端点搜索。

设状态$(x,y,z)$表示该考虑$S$串的$x$位置和$T$串的$y$位置，前面已经做了$k$次修改。

每层搜索开始先把$x$和$y$指针往后跳，跳的距离为后缀$x$和后缀$y$的$lcp$的长度。

如果有$x$或者$y$有一个到底了，就说明匹配上了。

设$d$表示剩下的操作次数，较显然的是$d=k-z-(len_S-x)$。

在我们手里还剩下$d$次操作次数的情况下，实际上合法结束位置不仅仅是$y-1$，而是$[y-1-d,y-1+d]$这个区间。这个区间的长度最多只有$2\times k +1$，可以用个前缀和统计一下。

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (200009)  5 #define LL long long  6 using namespace std;  7   8 int n,m=125,k,sl,tl,L,R,now,sum[N];  9 int wa[N],wb[N],wt[N]; 10 int ST[N][18],LOG2[N]; 11 int SA[N],Rank[N],Height[N]; 12 LL ans; 13 char r[N],s[N],t[N]; 14  15 bool cmp(int *y,int a,int b,int k) 16 { 17     int arank1=y[a]; 18     int brank1=y[b]; 19     int arank2=a+k>=n?-1:y[a+k]; 20     int brank2=b+k>=n?-1:y[b+k]; 21     return arank1==brank1 && arank2==brank2; 22 } 23  24 void Build_SA() 25 { 26     int *x=wa,*y=wb; 27     for (int i=0; i
        
         =0; --i) SA[--wt[x[i]]]=i; 31      32     for (int j=1; j<=n; j<<=1) 33     { 34         int p=0; 35         for (int i=n-j; i
         
          =j) y[p++]=SA[i]-j; 37          38         for (int i=0; i
          
           =0; --i) SA[--wt[x[y[i]]]]=y[i]; 42 43 m=1; swap(x,y); x[SA[0]]=0; 44 for (int i=1; i
           
            =n) break; 47 } 48 } 49 50 void Build_Height() 51 { 52 for (int i=0; i
            
             >1]+1; 67 for (int i=0; i
             
              k) return; 83 int l=Rank[x],r=Rank[y]; 84 if (l>r) swap(l,r); 85 int lcp=Query(l+1,r); 86 x+=lcp; y+=lcp; 87 if (x==sl || y==n) 88 { 89 int d=k-z-(sl-x); 90 if (d<0) return; 91 int l=max(y-1-d,now),r=min(y-1+d,n-1); 92 L=min(l,L); R=max(r+1,R); 93 sum[l]++; sum[r+1]--; 94 return; 95 } 96 DFS(x+1,y,z+1); DFS(x,y+1,z+1); DFS(x+1,y+1,z+1); 97 } 98 99 int main()100 {101 scanf("%d%s%s",&k,s,t);102 sl=strlen(s); tl=strlen(t);103 for (int i=0; i
              
               0;111 for (int j=L; j<=R; ++j) sum[j]=0;112 }113 printf("%lld\n",ans);114 }