UVA - 10391 Compound Words(复习STL)

题目传送门

两个想法1.合词2.拆词。因为合词的复制度时n^2所以我们选择拆词吧我的代码用了好多STL。。。

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
map<string, int> mmp;
int main(void)
{
	string str;

	while (cin >> str)mmp[str]++;//读入每个字符串
	map<string, int>::iterator it;

	for (it = mmp.begin(); it != mmp.end(); it++)
	{
		string temp = (*it).first;
		for (int i = 1; i < temp.size() - 1; i++)
		{
			string head = temp.substr(0, i);//将词分成两份
			string tail = temp.substr(i, temp.size());

			if (mmp.count(head) && mmp.count(tail)) { cout << temp << endl; break; }
			//观察两份到底是否出现在其中，若出现记得及时break
			//注意不能用mmp[head]和mmp[tail]因为这样会给mmp增加新的元素即使为0
		}
	}
	//system("pause");

	return 0;
}