1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005,K=20;
int sa[maxn],Rank[maxn],First[maxn],Second[maxn],Bucket[maxn],tmp[maxn],Height[maxn],Log2[maxn];
void Suffix_Array(int n,int* a) {
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[a[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)Rank[i]=Bucket[a[i]-1]+1;
for(int t=1; t<=n; t*=2) {
for(int i=1; i<=n; i++) {
First[i]=Rank[i];
Second[i]=(i+t)>n?0:Rank[i+t];
}
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[Second[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)tmp[n-(--Bucket[Second[i]])]=i;
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[First[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)sa[Bucket[First[tmp[i]]]--]=tmp[i];
bool unique=true;
for(int j=1,last=0; j<=n; j++) {
int i=sa[j];
if(!last)Rank[i]=1;
else if(First[i]==First[last]&&Second[i]==Second[last])Rank[i]=Rank[last],unique=false;
else Rank[i]=Rank[last]+1;
last=i;
}
if(unique)break;
}
int k=0;
for(int i=1; i<=n; i++) {
if(Rank[i]==1)k=0;
else {
if(k>0)k--;
int j=sa[Rank[i]-1];
while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
}
Height[Rank[i]]=k;
}
}
int n,m,k,a[maxn],b[maxn],f[maxn][K],vst[maxn],pos,ans=0;
char A[maxn],B[maxn];
int LCP(int x,int y) {
x=Rank[x],y=Rank[y+n+1];
if(x>y)swap(x,y);
x++;
int k=Log2[y-x+1];
return min(f[x][k],f[y-(1<<k)+1][k]);
}
void Dfs(int x,int y,int z) {
if(x>n&&y<=m+1&&y>pos&&vst[y]!=pos)vst[y]=pos,ans++;
int lcp=LCP(x,y);
x+=lcp,y+=lcp;
for(int i=0; i<=min(k-z-(n-x+1),lcp-1); i++)
if(vst[y-i]!=pos&&y-i>pos)vst[y-i]=pos,ans++;
if(z==k)return;
if(x<=n)Dfs(x+1,y,z+1);
if(y<=m)Dfs(x,y+1,z+1);
if(x<=n&&y<=m)Dfs(x+1,y+1,z+1);
}
int main() {
k=Get_Int();
scanf("%s%s",A+1,B+1);
n=strlen(A+1),m=strlen(B+1);
int cnt=0;
for(int i=1; i<=n; i++)a[++cnt]=A[i];
a[++cnt]='#';
for(int i=1; i<=m; i++)a[++cnt]=B[i];
copy(a+1,a+cnt+1,b+1);
sort(a+1,a+cnt+1);
int tot=unique(a+1,a+cnt+1)-a-1;
for(int i=1; i<=cnt; i++)b[i]=lower_bound(a+1,a+tot+1,b[i])-a;
Suffix_Array(cnt,b);
Log2[1]=0;
for(int i=2; i<=cnt; i++)Log2[i]=Log2[i>>1]+1;
for(int i=1; i<=cnt; i++)f[i][0]=Height[i];
for(int j=1; j<K; j++)
for(int i=1; i+(1<<(j-1))<=cnt; i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
for(pos=1; pos<=m; pos++)Dfs(1,pos,0);
printf("%d\n",ans);
return 0;
}
|
