http://acm.hdu.edu.cn/showproblem.php?pid=1075
C++版本一
题解:字典树||map
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=500000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int a[N][26];
char str[N],rec[N],str1[N],str2[N];
map<string,string>p;
bool en[N];
char cp[N][20];
void insert(char *s,char *s2){
int len=strlen(s),p=0;
for(int i=0;i<len;i++){
int ch=s[i]-'a';
if(a[p][ch]==0)a[p][ch]=++cnt;
p=a[p][ch];
}
en[p]=1;
strcpy(cp[p],s2);
}
void search(char* s){
int len=strlen(s),p=0;
for(int i=0;i<len;i++){
int ch=s[i]-'a';
if(a[p][ch]==0){
printf("%s",s);
return;
}
p=a[p][ch];
}
if(en[p])
printf("%s",cp[p]);
else
printf("%s",s);
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//scanf("%d",&n);
//scanf("%d",&t);
//while(t--){}
scanf("%s",str);
while(scanf("%s",str)){
if(strcmp(str,"END")==0)
break;
scanf("%s",str2);
insert(str2,str);
}
scanf("%s",str);
getchar();
while (gets(str) && strcmp(str, "END")) {
int len = strlen(str);
int idx = 0;
for (int i=0;i<=len - 1;i++) {
if (islower(str[i])) {
rec[idx++] = str[i];
} else {
rec[idx] = 0;
search(rec);
idx = 0;
printf("%c", str[i]);
}
}
puts("");
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解:
可以用map赤裸裸地做,但是比较花费时间,虽然这题时间给了5s,map解法是能过的。
不过Trie解法500+ms,果然Trie字典树才是正解啊。
Trie入门题。
另外发现ios_base::sync_with_stdio(0)这句话是关闭IO同步的,如果把cin和gets混用就不同步...坑了好久..
#include <cstdio>
#include <cstring>
#include <cctype>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
string a, b;
char s[3010];
map<string, string> mp;
int main() {
// ios_base::sync_with_stdio(0);
cin >> a;
while (cin >> a) {
if (a == "END")
break;
cin >> b;
mp[b] = a;
}
cin >> a;
getchar();
while (1) {
gets(s);
if (!strcmp(s, "END"))
break;
int len = strlen(s);
a = "";
repf (i, 0, len - 1) {
if (islower(s[i])) {
a += s[i];
} else {
if (mp.find(a) != mp.end())
cout << mp[a];
else
cout << a;
a = "";
cout << s[i];
}
}
cout << endl;
}
return 0;
}
C++版本三
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;
const int N = 3010;
const int SIZE = 26;
// pointer trie
struct Node {
char* val;
Node *next[SIZE];
};
struct PTrie {
Node *root;
PTrie() { root = newNode(); }
void init() { del(root); root = newNode(); }
inline int idx(char c) { return c - 'a'; }
Node *newNode() {
Node *u = new Node;
repf (i, 0, SIZE - 1) {
u->next[i] = NULL;
}
u->val = NULL;
return u;
}
void insert(char *s, char *v) {
Node *u = root;
int len = strlen(s);
repf (i, 0, len - 1) {
int c = idx(s[i]);
if (u->next[c] == NULL)
u->next[c] = newNode();
u = u->next[c];
}
u->val = new char[11];
strcpy(u->val, v);
}
void find(char *s) {
Node*u = root;
int len = strlen(s);
repf (i, 0, len - 1) {
int c = idx(s[i]);
if (u->next[c] == NULL) {
printf("%s", s);
return;
}
u = u->next[c];
}
if (u->val)
printf("%s", u->val);
else
printf("%s", s);
}
void del(Node *rt) {
if (rt == NULL)
return;
else {
repf (i, 0, SIZE - 1)
if (rt->next[i])
del(rt->next[i]);
}
delete rt->val;
delete rt;
}
} trie;
char a[11], b[11];
char str[N], rec[N];
int main() {
// ios_base::sync_with_stdio(0);
scanf("%s", a);
while (scanf("%s %s\n", a, b) && strcmp(a, "END")) {
//cout << a << b << endl;
trie.insert(b, a);
}
while (gets(str) && strcmp(str, "END")) {
int len = strlen(str);
int idx = 0;
repf (i, 0, len - 1) {
if (islower(str[i])) {
rec[idx++] = str[i];
} else {
rec[idx] = 0;
trie.find(rec);
idx = 0;
printf("%c", str[i]);
}
}
puts("");
}
}