大意不再赘述。
思路:STL爆过去用了0.128s,一时竟然想不到字符串按长度赋值的库函数,不过写出来还是很快的,动态字典树0.056,哈希函数0.060,今天去新华书店看书回来的路上遇到三个好基友了,结果被他们拖出去玩了一晚上,本来还想瞒他们一阵呢,hia hia,尼玛,我的行踪再次暴露了, - -!~
手写哈希的时候注意一点,就是first数组的大小要与所写的MAXN的相等,这个BUG找了我好久,囧。。。
#include <iostream>/*map*/ #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <map> using namespace std; map<string, int> Map; int n; char str[120010][30]; void init() { Map.clear(); n = 0; } void read_case() { init(); while(~scanf("%s", str[n]) && strcmp(str[n], "END")) { Map[str[n]] = 1; n++; } } void find() { for(int i = 0; i < n; i++) { int len = strlen(str[i]); for(int j = 0; j < len; j++) { char temp1[30] = {'\0'}; char temp2[30] = {'\0'}; strncpy(temp1, str[i], j); strncpy(temp2, str[i]+j, len-j); if(Map[temp1] && Map[temp2]) { printf("%s\n", str[i]); break; } } } } void solve() { read_case(); find(); } int main() { solve(); return 0; }
#include <iostream>/*手写哈希*/ #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 10000003; int n; typedef unsigned long UL; int first[MAXN]; int next[120010]; char st[120010][30]; void init() { n = 0; memset(first, -1, sizeof(first)); } int ELHhash(char *key) { UL h = 0; while(*key) { h = (h<<4) + *key++; UL g = h & 0xf0000000L; if(g) h ^= g>>24; h &= ~g; } return h % MAXN; } int find(char *str) { int h = ELHhash(str); for(int v = first[h]; v != -1; v = next[v]) { if(!strcmp(st[v], str)) return 1; } return 0; } void insert(int s) { int h = ELHhash(st[s]); next[s] = first[h]; first[h] = s; } void read_case() { init(); while(~scanf("%s", st[n]) && strcmp(st[n], "END")) { insert(n); n++; } } void print() { for(int i = 0; i < n; i++) { int len = strlen(st[i]); for(int j = 0; j < len; j++) { char temp1[30] = {'\0'}; char temp2[30] = {'\0'}; strncpy(temp1, st[i], j); strncpy(temp2, st[i]+j, len-j); if(find(temp1) && find(temp2)) { printf("%s\n", st[i]); break; } } } } void solve() { read_case(); print(); } int main() { solve(); return 0; }