UVa 10391 - Compound Words(STL成员函数)

输入一个词典,找出其中所有的复合词。单词数量小于120000。

将所有的单词保存在一个set中,单次遍历,对每一个单词判断是否为合成词。

判断时分别判断单词前缀和后缀是否在set中出现,set中排好序了,所以查找时间复杂度为O(logn),总时间复杂度O(nlogn),不会超时。

set.find()返回查找元素的迭代器,未找到返回set.end()。s.substr()返回s中的一段连续子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
#include<set>
using namespace std;
set<string>dict;
int main(){
string s;
while(cin>>s)
dict.insert(s);
s.clear();
for(set<string>::iterator it=dict.begin();it!=dict.end();it++){
s=*it;
for(int i=1;i<s.length();i++){
if(dict.find(s.substr(0,i))!=dict.end()&&dict.find(s.substr(i,s.length()-i))!=dict.end()){
cout<<s<<endl;
break;
}
}
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包