自动搬运

查看原文

来自洛谷，原作者为

	Jelly_Goat 小金羊！

搬运于2025-08-24 21:22:12，当前版本为作者最后更新于2019-02-28 20:31:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Upd 2019/3/2:
1.代码加上一些有利于理解的注释
2.有一些解释不清楚的重新解释或作出补充。

好！机会来了！

依评论区的要求，小金羊献上STLset<string>的题解。

当然不会告诉你map<string,bool>我根本不会用
所以，有什么STL救救孩子？？？

还是先复习 or 预习一下set。

先给set一个名字：

set<元素类型>qwq;

插入元素：

qwq.insert(元素);

查找元素：

qwq.find(元素);

如果元素没有找到，返回qwq.end()，是一个空的位置迭代器。
注：
1.迭代器可以看作是一个复合类型的指针，set的存储是动态线性的。
2.集合的最后一个元素是空的，qwq.end()指向最后一个元素。
3.如果找到元素，就会返回指向这个元素的指针，没有的话就返回qwq.end()。
于是得出： 如何判断元素p是否存在于qwq中？

if (qwq.find(p)!=qwq.end())
{
	//如果返回了qwq的end()，就代表是不存在。
	//所以不是end()就代表在qwq内
	//然后如果没有元素，就返回end()，避免了一些不必要的尴尬
	cout<<"p s in qwq."<<endl;
}
else 
	cout<<"Not found p in qwq."<<endl;

以上是这个题的STLset内置成员函数方面。

然后讨论一下这个题的操作。

这个题很明显卡的就是Windows Vista\XP\2003\7\8.1\10！！！
Linux系统13号是'\n',即换行......
因为题目测试点下载以后win会发现多了一个13号字符' '(空格)......
然后我们读入数据就必须特判（吃掉或者加上）char(13)。
然后每一个地方还不一定不含有空格，所以必须getline。
举个例子：Boston Center
cin读到Boston就停下了。
我们也可以读入一个' '就继续cin，然而getline更方便qwq
边读入要匹配的字符串，然后.find(input)判断是否存在，存在即ans++。

说的还是挺明白的吧......
星,上代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
//STL の set 库

using namespace std;

int main()
{
	string input;//你要的字符串
	set<string>qwq;//你要的集合
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	getline(cin,input);//把数字后面乱七八糟的东西读干净
	for (register int i=1;i<=n;i++)
	{
		getline(cin,input);//读入字符串
		if (input[input.size()-1]!=(char)13)//最后一个是否是' '
			input=input+char(13);
		qwq.insert(input);//压入集合qwq
	}
	for (register int i=1;i<=m;i++)
	{
		getline(cin,input);
		if (input[input.size()-1]!=(char)13)//最后一个是否是' '
			input=input+char(13);
		if (qwq.find(input)!=qwq.end())ans++;
	}
	cout<<ans;
	return 0;
}

瞎举报前提交记录自己查询：Jelly_Goat。
感谢阅读，更多精彩移步。

另附后注：

做这样的字符串匹配问题，trie字典树和KMP算法基本都是正解。
但是这样的数据结构是用空间换时间，当字符串过长的时候，不宜使用静态Trie字典树。
当数据范围较小的时候，我们可以借助其他数据结构用时间换空间。