rt，用结构体：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;

namespace ac{
	struct node{
		int fail;
		int nxt[31];
		int val;
	}AC[N];
	char s[N * 200 / 3];
	int dp[N * 200 / 3];
	int tot = 0,max_len = 0;
	void insert(int len){
		int now = 0;
		for (int i = 1;i <= len;++i){
			int c = s[i] - 'a';
			if (!AC[now].nxt[c]) AC[now].nxt[c] = ++tot;
			now = AC[now].nxt[c];
		}
		AC[now].val = len;
		max_len = max(max_len,len);
		return;
	}
	int st = 0,ed = 0;
	int q[N * 200 / 3];
	void bfs(){
		for (int i = 0;i < 26;++i) if (AC[0].nxt[i]) AC[AC[0].nxt[i]].fail = 0,q[++ed] = AC[0].nxt[i];
		while (st < ed){
			int r = q[++st];
			//cout << r << endl;
			for (int i = 0;i < 26;++i){
				if (AC[r].nxt[i]){
					AC[AC[r].nxt[i]].fail = AC[AC[r].fail].nxt[i];
					q[++ed] = AC[r].nxt[i];
				}
				else AC[r].nxt[i] = AC[AC[r].fail].nxt[i];
			}
		}
		return;
	}
	int ans = 0,now,c;
	int query(int len){
		for (int i = 1;i <= len;++i) dp[i] = 0;
		dp[0] = 1;
		ans = now = 0;
		for (int i = 1;i <= len;++i){
			//cout << i <<endl;
			if (ans + max_len < i) break;
			c = s[i] - 'a';
			now = AC[now].nxt[c];
			for (int j = now;j;j = AC[j].fail){
				dp[i] |= dp[i - AC[j].val];
				if (dp[i]) break;
			}
			if (dp[i]) ans = i;
		}
		return ans;
	}
}
inline void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10,x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);
}
int n,m;
int main(){
	using namespace ac;
	cin >> n >> m;
	while (n--){
		scanf("%s",s + 1);
		insert(strlen(s + 1));
	}
	//AC[0].fail = 0;
	bfs();
	while (m--){
		scanf("%s",s + 1);
		write(query(strlen(s + 1)));
		puts("");
	}
}

结果95分。

不用结构体：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;

namespace ac{
	int fail[N];
	int nxt[N][31];
	int val[N];
	char s[N * 200 / 3];
	int dp[N * 200 / 3];
	int tot = 0,max_len = 0;
	void insert(int len){
		int now = 0;
		for (int i = 1;i <= len;++i){
			int c = s[i] - 'a';
			if (!nxt[now][c]) nxt[now][c] = ++tot;
			now = nxt[now][c];
		}
		val[now] = len;
		max_len = max(max_len,len);
		return;
	}
	int st = 0,ed = 0;
	int q[N * 200 / 3];
	void bfs(){
		for (int i = 0;i < 26;++i) if (nxt[0][i]) fail[nxt[0][i]] = 0,q[++ed] = nxt[0][i];
		while (st < ed){
			int r = q[++st];
			//cout << r << endl;
			for (int i = 0;i < 26;++i){
				if (nxt[r][i]){
					fail[nxt[r][i]] = nxt[fail[r]][i];
					q[++ed] = nxt[r][i];
				}
				else nxt[r][i] = nxt[fail[r]][i];
			}
		}
		return;
	}
	int ans = 0,now,c;
	int query(int len){
		for (int i = 1;i <= len;++i) dp[i] = 0;
		dp[0] = 1;
		ans = now = 0;
		for (int i = 1;i <= len;++i){
			//cout << i <<endl;
			if (ans + max_len < i) break;
			c = s[i] - 'a';
			now = nxt[now][c];
			for (int j = now;j;j = fail[j]){
				dp[i] |= dp[i - val[j]];
				if (dp[i]) break;
			}
			if (dp[i]) ans = i;
		}
		return ans;
	}
}
inline void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10,x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);
}
int n,m;
int main(){
	using namespace ac;
	cin >> n >> m;
	while (n--){
		scanf("%s",s + 1);
		insert(strlen(s + 1));
	}
	//AC[0].fail = 0;
	bfs();
	while (m--){
		scanf("%s",s + 1);
		write(query(strlen(s + 1)));
		puts("");
	}
}

就AC了。

为什么？