至于那个unordered_map,,,要看数据了,如果存1000万个数据准得爆掉QwQ
by t162 @ 2019-02-17 19:02:15
@[Bambusoideae](/space/show?uid=106140)
重点是本机测试最大峰值内存只有 $\text{100MB}$ 左右,交上去为什么会 $\text{MLE}$ 啊QAQ
by ✡Dustaria✡ @ 2019-02-17 19:02:45
@[✡Dustaria✡](/space/show?uid=89309) ~~评测姬心情不好(开溜~~
by t162 @ 2019-02-17 19:04:27
@[✡Dustaria✡](/space/show?uid=89309) 动态表申请内存需要倍增吧qaq
by 皎月半洒花 @ 2019-02-17 19:04:32
@[✡Dustaria✡](/space/show?uid=89309) 我觉得可能本机评测自动收缩冗余空间的锅qaq
by 皎月半洒花 @ 2019-02-17 19:05:15
$\text{UPD:}$
把`std::unordered_map` 换掉,写成下面这个样子就能 $\text{AC}$ 第一个点......
但是重点仍然是本地测试峰值内存只有 $\text{100MB}$ 啊QAQ
难道`std::unordered_map`在洛谷的评测姬上内存会变大很多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];
int ch[maxn][2];
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;
memcpy(ch[nq],ch[q],sizeof(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;
}
```
by ✡Dustaria✡ @ 2019-02-17 19:07:46
@[_皎月半洒花](/space/show?uid=28313)
也许只能这么解释了吧...感谢
by ✡Dustaria✡ @ 2019-02-17 19:08:47
找到主要问题了@[✡Dustaria✡](/space/show?uid=89309)
by FizzyDAVlD @ 2019-02-17 19:37:45
你开1e6个string不怕吗
by FizzyDAVlD @ 2019-02-17 19:38:24
全部存下来1e12不MLE就怪了
by FizzyDAVlD @ 2019-02-17 19:39:22