题解

好神仙的题啊

感觉转二维平面能想到，算重复情况的方法真想不到啊

通过扒stdcall代码获得的题解QAQQQQ

我们先把\(p_i\)正串反串建出一个AC自动机来

然后我们把s串放在上面跑匹配，正着跑一遍，反着跑一遍，我们就得到了\(s\)中每个位置正着和反着能匹配到的节点编号

然后对于AC自动机，我们建出fail树来，并处理出每个点在fail树上dfs序

对于AC自动机上的一个点，我们把\(p_i\)正串的询问挂在上面，假如这个点的匹配深度为x，那么我们就需要对于这个点fail树里所有匹配到的\(s\)中正着匹配到的位置，问这个位置a，\(a + k + 1\)是不是在\(p_i\)反串\(x + k + 1\)(也是原下标）所在AC自动机节点fail树的子树里

举个例子

k = 3

假如\(p_i\)是

abacdefg

然后s中的一段是

abahdefg

我们找到\(p_i\)在AC自动机中aba所在的节点，挂上\(p_i\)这个询问，找出所有这个节点fail树里匹配到的s正串的位置\(a\)

查询的是\(p_i\)反串gfe所在节点fail树子树里，问\(a + k + 1\)有多少个

这个可以通过树状数组维护，问一个点子树里的只要用遍历子树后的值减掉遍历子树前的值就好

然而……你发现这样统计会有重复了吗

还是刚刚那个例子

我们发现，当我们在a所在的节点时，我们还会计算一遍这一段

为了去重，我们使得左边匹配要到达最长，也就是，如果这个位置\(a + k\)也合法的话，那么我们要减掉它

就是在aba这个点，同时挂上gfed节点，然后减掉这些方案

维护方法还是树状数组，和上面类似

代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define pdi pair<db,int>

#define mp make_pair

#define pb push_back

#define enter putchar('\n')

#define space putchar(' ')

#define eps 1e-8

#define MAXN 200005

#define mo 974711

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int L[MAXN],R[MAXN],K,N,dfn[MAXN * 2],idx,siz[MAXN * 2],H,ans[MAXN],pos[2][MAXN];

char s[MAXN],t[MAXN];

vector<int> son[MAXN * 2];

vector<int> ver[MAXN * 2];

vector<pii > Qry[MAXN * 2];

int sum[2][MAXN * 2];

namespace ACAM {

    int tr[MAXN * 2][94],fail[MAXN * 2],Ncnt,rt,que[MAXN * 2],ql,qr;

    void Init() {

	Ncnt = 1,rt = 1;

    }

    int ins(int p,int c) {

	if(!tr[p][c]) tr[p][c] = ++Ncnt;

	return tr[p][c];

    }

    void build_ACAM() {

	ql = 1,qr = 0;

	que[++qr] = 1;fail[1] = 1;

	while(ql <= qr) {

	    int u = que[ql++];

	    for(int i = 0 ; i <= 93 ; ++i) {

		if(tr[u][i]) {

		    int v = tr[u][i];

		    int t = fail[u];

		    if(u == 1) fail[v] = 1;

		    else {

			while(1) {

			    if(tr[t][i]) {fail[v] = tr[t][i];break;}

			    if(t == 1) {fail[v] = 1;break;}

			    t = fail[t];

			}

		    }

		    que[++qr] = v;

		    son[fail[v]].pb(v);

		}

	    }

	}

    }

}

using ACAM::ins;

void dfs(int u) {

    dfn[u] = ++idx;siz[u] = 1;

    int s = son[u].size();

    for(int i = 0 ; i < s ; ++i) {

	dfs(son[u][i]);

	siz[u] += siz[son[u][i]];

    }

}

int lowbit(int x) {return x & (-x);}

void insert(int on,int x) {

    while(x <= ACAM::Ncnt) {

	sum[on][x]++;

	x += lowbit(x);

    }

}

int Query(int on,int x) {

    int res = 0;

    while(x > 0) {

	res += sum[on][x];

	x -= lowbit(x);

    }

    return res;

}

int Query_Range(int on,int x) {

    return Query(on,dfn[x] + siz[x] - 1) - Query(on,dfn[x] - 1);

}

void Process(int u) {

    int s = Qry[u].size();

    for(int i = 0 ; i < s ; ++i) {

	if(Qry[u][i].se > 0) ans[Qry[u][i].fi] -= Query_Range(0,Qry[u][i].se);

	if(Qry[u][i].se < 0) ans[Qry[u][i].fi] += Query_Range(1,-Qry[u][i].se);

    }

    s = ver[u].size();

    for(int i = 0 ; i < s ; ++i) {

	if(ver[u][i] > 0) insert(0,dfn[ver[u][i]]);

	if(ver[u][i] < 0) insert(1,dfn[-ver[u][i]]);

    }

    s = son[u].size();

    for(int i = 0 ; i < s ; ++i) {

	Process(son[u][i]);

    }

    s = Qry[u].size();

    for(int i = 0 ; i < s ; ++i) {

	if(Qry[u][i].se > 0) ans[Qry[u][i].fi] += Query_Range(0,Qry[u][i].se);

	if(Qry[u][i].se < 0) ans[Qry[u][i].fi] -= Query_Range(1,-Qry[u][i].se);

    }

}

void Solve() {

    read(K);

    scanf("%s",s + 1);

    H = strlen(s + 1);

    read(N);

    ACAM::Init();

    for(int i = 1 ; i <= N ; ++i) {

	scanf("%s",t + 1);

	int len = strlen(t + 1);

	int p = 1;

	if(len > K) {

	    for(int j = 1 ; j <= len ; ++j) {

		p = ins(p,t[j] - 33);

		L[j] = p;

	    }

	    p = 1;

	    for(int j = len ; j >= 1 ; --j) {

		p = ins(p,t[j] - 33);

		R[j] = p;

	    }

	    for(int j = 0 ; j <= len - K; ++j) {

		int a = j == 0 ? 1 : L[j];

		int b = j + K + 1 == len + 1 ? 1 : R[j + K + 1];

		Qry[a].pb(mp(i,b));

	    }

	    for(int j = 1 ; j <= len - K; ++j) {

		int a = L[j],b = R[j + K];

		Qry[a].pb(mp(i,-b));

	    }

	}

	else ans[i] = H - len + 1;

    }

    ACAM::build_ACAM();

    int p = 1;

    pos[0][0] = 1;

    for(int i = 1 ; i <= H ; ++i) {

	while(1) {

	    if(ACAM::tr[p][s[i] - 33]) {p = ACAM::tr[p][s[i] - 33];break;}

	    else if(p == 1) break;

	    p = ACAM::fail[p];

	}

	pos[0][i] = p;

    }

    p = 1;

    pos[1][H + 1] = 1;

    for(int i = H ; i >= 1 ; --i) {

	while(1) {

	    if(ACAM::tr[p][s[i] - 33]) {p = ACAM::tr[p][s[i] - 33];break;}

	    else if(p == 1) break;

	    p = ACAM::fail[p];

	}

	pos[1][i] = p;

    }

    dfs(1);

    for(int i = 0 ; i <= H - K; ++i) {

	ver[pos[0][i]].pb(pos[1][i + K + 1]);

    }

    for(int i = 1 ; i <= H - K; ++i) {

	ver[pos[0][i]].pb(-pos[1][i + K]);

    }

    Process(1);

    for(int i = 1 ; i <= N ; ++i) {

	out(ans[i]);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}