You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.
Output
Your output should contain all the compound words, one per line, in alphabetical order.
Sample Input
a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
题目类型：二分查找
算法分析：由于数据规模有12e4，所以考虑按照字典序对于每个单词构造出其相接的子串sa和sb，然后二分查找sa和sb是否在给定的数据集中，复杂度为O(nmlogn)，n为单词个数，m为单词长度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
/************************************************** filename :e.cpp author :maksyuki created time :2018/1/22 21:06:11 last modified :2018/1/22 21:12:34 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; set<string> dict; int main() { #ifdef LOCAL CFF; //CFO; #endif string s; while(cin >> s) { if(!dict.count(s)) dict.emplace(s); } string sa, sb, sc; for(set<string>:: iterator it = dict.begin(); it != dict.end(); it++) { sa = *it; int len = sa.size(); bool is_find = false; for(int i = 1; i < len; i++) { sb = sa.substr(0, i); sc = sa.substr(i, len - i); if(dict.count(sb) && dict.count(sc)) { is_find = true; break; } } if(is_find) cout << *it << endl; } return 0; } |
- « 上一篇：uva10763
- uva1595：下一篇 »