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
|
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int (char c){
if(c=='A')return 0;if(c=='T')return 1;if(c=='C')return 2;if(c=='G')return 3;
}
char s1[maxn],s2[maxn];
int len1,len2;
struct SAM{
int pa[maxn<<1],son[maxn<<1][4];
int deep[maxn<<1],cnt,root,last;
int sum[maxn<<1],topo[maxn<<1];
int r[maxn<<1];
inline int newnode(int _deep){
deep[++cnt]=_deep;
return cnt;
}
inline void sam(int alp){
int np=newnode(deep[last]+1);
int u=last;
memset(son[np],0,sizeof son[np]);
while(u&&!son[u][alp])son[u][alp]=np,u=pa[u];
if(!u)pa[np]=root;
else{
int v=son[u][alp];
if(deep[v]==deep[u]+1)pa[np]=v;
else{
int nv=newnode(deep[u]+1);
memcpy(son[nv],son[v],sizeof son[v]);
pa[nv]=pa[v],pa[v]=pa[np]=nv;
while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
}
}last=np;
}
inline void pre(){
cnt=0;
memset(son[1],0,sizeof son[1]);
root=last=newnode(0);
memset(r,0,sizeof r);
}
inline void toposort(){
int tmp=root;
for(int a=0;a<len1;a++){
tmp=son[tmp][tran(s1[a])];
r[tmp]=1;
}
memset(sum,0,sizeof sum);
for(int a=1;a<=cnt;a++)sum[deep[a]]++;
for(int a=1;a<=deep[last];a++)sum[a]+=sum[a-1];
for(int a=1;a<=cnt;a++)topo[sum[deep[a]]--]=a;
for(int a=cnt;a>=1;a--)r[pa[topo[a]]] += r[topo[a]];
}
}A;
int ans;
void dfs(int pos1,int pos2,int lim){
if(lim>3)return;
if(pos2==len2){
ans+=A.r[pos1];return;
}
for(int a=0;a<4;a++){
if(A.son[pos1][a]){
dfs(A.son[pos1][a],pos2+1,lim+(a!=tran(s2[pos2])));
}
}
}
int main(){
int t;cin>>t;
while(t--){
ans=0;
scanf("%s%s",s1,s2);
A.pre();
len1=strlen(s1);len2=strlen(s2);
for(int i=0;i<len1;i++)A.sam(tran(s1[i]));
A.toposort();
dfs(1,0,0);
printf("%dn",ans);
}
return 0;
}
|
近期评论