嘟嘟嘟
这题怎么想都想不出来，最后还是敲了暴力，喜提40分……
正解竟然也是暴力……
用(s_0)构造SAM，然后把(s)扔上去暴力dfs：记录一个修改次数tot，如果当前不匹配，就tot + 1并且往下跳……
反正就是过了……
记得多组数据，清空数组。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, ans = 0, val[200];
char s[maxn];
struct Sam
{
int las, cnt;
int tra[maxn << 1][5], len[maxn << 1], link[maxn << 1], siz[maxn << 1];
In void insert(int c)
{
int now = ++cnt, p = las;
len[now] = len[las] + 1; siz[now] = 1;
while(~p && !tra[p][c]) tra[p][c] = now, p = link[p];
if(p == -1) link[now] = 0;
else
{
int q = tra[p][c];
if(len[q] == len[p] + 1) link[now] = q;
else
{
int clo = ++cnt;
len[clo] = len[p] + 1;
memcpy(tra[clo], tra[q], sizeof(tra[q]));
link[clo] = link[q], link[q] = link[now] = clo;
while(~p && tra[p][c] == q) tra[p][c] = clo, p = link[p];
}
}
las = now;
}
int buc[maxn << 1], pos[maxn << 1];
In void sort()
{
for(int i = 1; i <= cnt; ++i) ++buc[len[i]];
for(int i = 1; i <= cnt; ++i) buc[i] += buc[i - 1];
for(int i = 1; i <= cnt; ++i) pos[buc[len[i]]--] = i;
for(int i = cnt; i; --i) siz[link[pos[i]]] += siz[pos[i]];
}
In void dfs(int p, int len, int tot)
{
if(tot > 3) return;
if(len >= m) {ans += siz[p]; return;}
for(int c = 1; c <= 4; ++c)
{
if(!tra[p][c]) continue;
if(c == val[s[len]]) dfs(tra[p][c], len + 1, tot);
else dfs(tra[p][c], len + 1, tot + 1);
}
}
In void init()
{
Mem(tra, 0), Mem(link, 0), Mem(len, 0), Mem(siz, 0);
link[las = cnt = 0] = -1;
Mem(buc, 0), Mem(pos, 0);
}
}S;
int main()
{
val['A'] = 1, val['T'] = 2, val['G'] = 3, val['C'] = 4;
int T = read();
while(T--)
{
S.init(); ans = 0;
scanf("%s", s); n = strlen(s);
for(int i = 0; i < n; ++i) S.insert(val[s[i]]);
S.sort();
scanf("%s", s); m = strlen(s);
S.dfs(0, 0, 0);
write(ans), enter;
}
return 0;
}