返回信息流学习刘汝佳的入门一书。
uva10391题， https://vjudge.net/problem/UVA-10391
用set 会超时， 用map就ac了。 请问下这是什么原因啊？
//方法一，用set。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
set<string> dict;
string item[120100];
int cnt = 0;
void solve(const set<string>& d)
{
for(int t = 0; t < cnt; ++t)
{
string word = item[t];
int ok = 0;
for(int i = 1; i < word.length(); ++i)
{
string s1 = word.substr(0, i);
string s2 = word.substr(i);
if ( find(dict.begin(),dict.end(),s1) != dict.end() && find(dict.begin(), dict.end(), s2) != dict.end())
{
ok = 1;
break;
}
}
if(ok)
cout<<word<<endl;
}
}
int main(int argc, char* argv[])
{
string s;
while(cin>>s){
dict.insert(s);
item[cnt++] = s;
}
solve(dict);
return 0;
}
//方法二，用map
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
map<string, int> dict;
string item[120100];
int cnt = 0;
void solve(const map<string, int>& d)
{
char temp[100];
for(int t = 0; t < cnt; ++t)
{
string word = item[t];
int ok = 0;
for(int i = 1; i < word.length(); ++i)
{
string s1 = word.substr(0, i);
string s2 = word.substr(i);
if (dict[s1] && dict[s2])
{
ok = 1;
break;
}
}
if(ok)
cout<<word<<endl;
}
}
int main(int argc, char* argv[])
{
string s;
while(cin>>s){
dict[s] = 1;
item[cnt++] = s;
}
solve(dict);
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #93599同步于 2017/6/6
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教， uva10391 用set 为什么会超时？
bj
2017/6/6镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
难道 这个 std::find()是线性查找咩。。
【 在 Macaulish64 的大作中提到: 】
: 此find非彼find……应该是dict.find()233333.
yeah, done!!
void solve(const set<string>& dict)
{
for(int t = 0; t < cnt; ++t)
{
string word = item[t];
int ok = 0;
for(int i = 1; i < word.length(); ++i)
{
string s1 = word.substr(0, i);
string s2 = word.substr(i);
//if ( find(dict.begin(),dict.end(),s1) != dict.end() && find(dict.begin(), dict.end(), s2) != dict.end())
if(dict.find(s1) != dict.end() && dict.find(s2) != dict.end())
{
ok = 1;
break;
}
}
if(ok)
cout<<word<<endl;
}
}
【 在 Macaulish64 的大作中提到: 】
: 此find非彼find……应该是dict.find()233333.