玄关 求调

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 1e06 * 5 + 7;
int n, q, alen;
char s[MAXN], t[MAXN], ss[MAXN], tt[MAXN], a[MAXN];
int cnt, tr[MAXN][29], val[MAXN], fail[MAXN];
void trs(char *s, char *t)
{
	int ct = 0;
	int len = strlen(s + 1);
	int st = 1, ed = len;
	for(int i = 1; i <= n; i++)
	{
		if(s[i] == t[i])
			a[++ct] = s[i];
		else
		{
			st = i;
			break;
		}
	}
	for(int i = len; i >= 1; i--)
	{
		if(s[i] != t[i])
		{
			ed = i;
			break;
		}
	}
	a[++ct] = '{';
	for(int i = st; i <= ed; i++)
		a[++ct] = s[i];
	for(int i = st; i <= ed; i++)
		a[++ct] = t[i];
	a[++ct] = '{';
	for(int i = ed + 1; i <= len; i++)
		a[++ct] = s[i];
	alen = ct;
	return ;
}
void ins(char *s)
{
    int p = 0;
    for(int i = 1; i <= alen; i++)
    {
        int c = s[i] - 'a' + 1;
        if(!tr[p][c])
            tr[p][c] = ++cnt;
        p = tr[p][c];
    }
    val[p]++;
    return ;
}
void getFail()
{
	queue <int> q;
	for(int i = 1; i <= 27; i++)
	{
		if(tr[0][i])
		{
			fail[tr[0][i]] = 0;
			q.push(tr[0][i]);
		}
	}
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 1; i <= 27; i++)
		{
			if(tr[u][i])
			{
				fail[tr[u][i]] = tr[fail[u]][i];
				q.push(tr[u][i]);
			}
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
	return ;
}
int qry(char *t)
{
	int p = 0, res = 0;
	for(int i = 1; i <= alen; i++)
	{
		int c = t[i] - 'a' + 1;
		p = tr[p][c];
		for(int j = p; j and val[j] != -1; j = fail[j])
			res += val[j];
	}
	return res;
}
signed main()
{
//	freopen("replace.in", "r", stdin);
//	freopen("replace.out", "w", stdout);
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++)
	{
		bool flg = false;
		scanf("%s%s", s + 1, ss + 1);
		int len = strlen(s + 1);
		for(int j = 1; j <= len; j++)
		{
			if(s[j] != ss[j])
			{
				flg = true;
				break;
			}
		}
		if(!flg)
			continue;
		trs(s, ss);
		ins(a);
	}
	getFail();
	while(q--)
	{
		scanf("%s%s", t + 1, tt + 1);
		trs(t, tt);
		printf("%d\n", qry(a));
	}
	return 0;
}