AC自动机

#include <cstdio>
#include <cstring>
#include <queue>
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=n;i>=a;--i)
#define for4(i,a,n) for(i=n;i>a;--i)
#define CC(i,a) memset(i, a, sizeof(i))

using namespace std;

const int N=10000000, Type=26;
char a[N], b[N];
int ch[N][Type], fail[N], w[N], ans, cnt=1;
queue<int> q;

void ins(char* s) {
	int u=0, v, i, len=strlen(s);
	for2(i, 0, len) {
		v=s[i]-‘a‘;
		if(!ch[u][v]) ch[u][v]=cnt++;
		u=ch[u][v];
	}
	w[u]++;
}

void bfs() {
	fail[0]=0;
	q.push(0);
	int u, p, i;
	while(!q.empty()) {
		u=q.front(); q.pop();
		for2(i, 0, Type) if(ch[u][i]) {
			q.push(ch[u][i]); //先插入，后判断
			if(!u) continue; //不要在这里错了。。
			p=fail[u];
			while(p && !ch[p][i]) p=fail[p];
			fail[ch[u][i]]=ch[p][i];
		}
	}
}

void ac(char* s) {
	int i, u=0, v, len=strlen(s), t;
	for2(i, 0, len) {
		v=s[i]-‘a‘;
		while(u && !ch[u][v]) u=fail[u];
		u=ch[u][v];
		t=u;
		while(t) {
			ans+=w[t];
			w[t]=0;
			t=fail[t];
		}
	}

}

void init() {
	CC(fail, 0);
	CC(ch, 0);
	CC(w, 0);
}

int main() {
	init();
	scanf("%s", a);
	int n, i;
	scanf("%d", &n);
	for1(i, 1, n) {
		scanf("%s", b);
		ins(b);
	}
	bfs();
	ac(a);
	printf("%d\n", ans);
	
	return 0;
}