萌新刚学OI (x，请问......

这题卡

\text{SAM}

空间没关系，毕竟是

\text{AC}

自动机的模板题

可是第一个测试点数据的字符集大小只有

1

，也就是说

\text{SAM}

的节点个数只有

1000001

，所以如果只看第一个测试点那么下面这份代码的数组是开够了的

但是让我搞不懂的是为什么

\text{MLE}

了啊......关键是把第一个点的数据下载下来在本地测一点问题也没有......

如下图，本地测试时内存峰值只有大约

\text{101MB}

，但是在洛谷上就是

\text{MLE}

了QAQ

希望有神仙能告诉蒟蒻为什么QAQ，不胜感激

CPP

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <iostream>
#include <string>
using namespace std;

const int maxn=1000005;

int n;
int Ans;
string sr;
string ss[maxn];

struct SAM{
	int tot;
	int last;
	int len[maxn<<1];
	int prt[maxn<<1];
	unordered_map<char,int> ch[maxn];
	inline SAM(){
		tot=last=1;
	}
	inline void Insert(int x){
		int p=last,np=++tot;
		len[last=np]=len[p]+1;
		while(p&&(!ch[p][x]))
			ch[p][x]=np,p=prt[p];
		if(!p) prt[np]=1;
		else{
			int q=ch[p][x];
			if(len[q]==len[p]+1) prt[np]=q;
			else{
				int nq=++tot;
				len[nq]=len[p]+1;ch[nq]=ch[q];
				prt[nq]=prt[q];prt[q]=prt[np]=nq;
				while(p&&ch[p][x]==q)
					ch[p][x]=nq,p=prt[p];
			}
		}
	}
	inline bool Query(const string& ss){
		for(int i=0,p=1;i<ss.size();++i){
			char x=ss[i]-'a';
			if(!ch[p][x]) return 0;
			p=ch[p][x];
		}
		return 1;
	}
}M;

void Work();

int main(){
	Work();
	return 0;
}

void Work(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>ss[i];
	cin>>sr;
	for(int i=0;i<sr.size();++i)
		M.Insert(sr[i]-'a');
	for(int i=1;i<=n;++i)
		Ans+=M.Query(ss[i]);
	cout<<Ans<<endl;
	while(1);
}

萌新刚学OI (x，请问......

讨论操作

回复

相关推荐

萌新刚学OI (x，请问......