如题

现写了一个自动机，但是无奈最后一组测试点超时超内存，实在没什么办法了。本来是想递归match，然后如果找到一个word，那么分支出去两个，一个直接完成匹配，跳到根节点重新匹配，一个继续当前点去匹配。然后最后总结一下，但是T到飞起。

后面写的就是一个AC自动机，然后把所有匹配到的单词的区间存进vector里面，然后就是一个区间覆盖问题了。

2-1测试点TLE，剩下的MLE，一组测试点全对，求大佬帮忙指点一下

#include<bits/stdc++.h>
using namespace std;
typedef struct AAA{
	AAA *fail;
	AAA *next[26];
	int is_word;
	int len;
	void a(){
		fail=NULL;
		for(int i=0;i<26;i++){
			next[i]=NULL;
		}
		is_word=0;
	}
}node;
typedef struct eee{
	int l,r;
}res;
node *root,*p,*tmp;
int title_len=0;
char word[25];
char title[2000003];
vector<res>ss;
void insert_word(){
	int len=strlen(word);
	p=root;
	for(int i=0;i<len;i++){
		if(!p->next[word[i]-'a']){
			tmp=new node;
			tmp->a();
			p->next[word[i]-'a']=tmp;
		}
		p=p->next[word[i]-'a'];
	}
	p->is_word=1;
	p->len=len;
}

void build_fail(){
	queue<node *>q;
	q.push(root);
	while(!q.empty()){
		node *p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(p->next[i]!=NULL){
				node *k=p->next[i]; 
				q.push(k);
				if(p==root){
					k->fail=root;
				}
				else{
					node *fafail=p->fail;
					while(fafail!=NULL){
						if(fafail->next[i]!=NULL){
							k->fail=fafail->next[i];
							break;
						}
						fafail=fafail->fail;
					}
					if(fafail==NULL)k->fail=root;
				}
			}
		}
	}
}

void match(){
	p=root;
	for(int i=0;i<title_len;i++){
		int k=title[i]-'a';
		while(p!=root&&p->next[k]==NULL)
		    p=p->fail;
		p=p->next[k];
		if(p==NULL)
		    p=root;
		node *temp=p;
		
		while(temp!=root){
			if(temp->is_word){
				ss.push_back({i-(temp->len)+1,i});
			}
			temp=temp->fail;
		}	
	}
}

int cmp(res a,res b){
	return a.l<b.l;
}

bool dp[2000010]; 
int main(){
    //freopen("1.in","r",stdin);
	int n,m;
	scanf("%d %d",&n,&m);
	root=new node;
	root->a();
	for(int i=1;i<=n;i++){
		scanf("%s",word);
		insert_word();
	}
	build_fail();
	dp[0]=1;
	
	while(m--){
		scanf("%s",title);
		title_len=strlen(title);
		ss.clear();
		match();
		int ans=-1;
		sort(ss.begin(),ss.end(),cmp);
		memset(dp,0,sizeof(dp));
		dp[0]=0;
		for(auto i=ss.begin();i!=ss.end();i++){
			//printf("l:%d r:%d\n",i->l,i->r);
			if(i->l==0||dp[i->l-1]){
				dp[i->r]=1;
				ans=max(ans,i->r);
			}
			
		}
		printf("%d\n",ans+1);
		
	}
	
	return 0;
}