AC自动机+暴力DP

#include<bits/stdc++.h>
using namespace std;
const int N = 3000005;
bool f[N];

namespace Trie{
	const int M = 100005;
	int trie[M][65];
	int data[M];
	int cur = 0;
	
	inline int T(char ch){
		if(ch >= '0' && ch <= '9') return ch - '0';
		if(ch >= 'a' && ch <= 'z') return ch - 'a' + 10;
		return ch - 'A' + 26 + 10;
	}
	
	void insert(const string& s){
		int len = s.length();
		int p = 0;
		for(int i = 0;i < len;++ i){
			int ch = T(s[i]);
			if(!trie[p][ch]) trie[p][ch] = ++ cur;
			p = trie[p][ch];
		}
		data[p] = len;
	}
}

namespace AC{
	using namespace Trie;
	int fail[M];
	
	void build(){
		queue<int> q;
		for(int i = 0;i < 65;++ i){
			if(trie[0][i]) q.push(trie[0][i]);
		}
		while(!q.empty()){
			int p = q.front();
			q.pop();
			for(int ch = 0;ch < 65;++ ch){
				if(trie[p][ch]){
					fail[trie[p][ch]] = trie[fail[p]][ch];
					q.push(trie[p][ch]);
				}
				else trie[p][ch] = trie[fail[p]][ch];
			}
		}
	}
	
	int query(const string& str){
		int len = str.length();
		int p = 0;
		f[0] = true;
		int ans = 0;
		for(int i = 0;i < len;++ i){
			int ch = T(str[i]);
			p = trie[p][ch];
			for(int j = p;j;j = fail[j]){
				int l = i + 1 - data[j] + 1;
				int r = i + 1;
				if(f[l - 1]){
					f[r] = true;
					ans = r;
				}
				j = fail[j];
			}
		}
		return ans;
	}
}

int main(){
	int n,T;
	cin>>n>>T;
	for(int i = 1;i <= n;++ i){
		string p;
		cin>>p;
		Trie::insert(p);
	}
	AC::build();
	while(T --){
		memset(f,0,sizeof(f));
		string str;
		cin>>str;
		cout<<AC::query(str)<<"\n";
	}
	return 0;
}