POJ 2418 Hardwood Species
题意：给一些字符串，按照字典序输出他们，并且输出频率...........
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
struct Trie {
int next[128];
int sum;
char s[33];
void init() {
memset(next,0,sizeof(next));
sum = 0;
}
} a[301111];
int num,cnt,root;
char str[33];
void insert(char *key) {
int p = root;
for(int i=0; key[i]; i++) {
int t = int(key[i]);
if(a[p].next[t] == 0) {
a[p].next[t] = ++ num;
a[num].init();
}
p = a[p].next[t];
}
a[p].sum ++;
a[p].s[0] = ' ';
strcpy(a[p].s,key);
}
void dfs(int p) {
if(a[p].sum != 0) {
printf("%s ",a[p].s);
printf("%.4f
",(a[p].sum * 1.0) / cnt * 100);
}
for(int i=0; i<128; i++) {
if(a[p].next[i] != 0) {
int t = a[p].next[i];
dfs(t);
}
}
}
int main() {
root = 0; num = 0; cnt = 0;
a[root].init();
while(gets(str)) {
int len = strlen(str);
if(len == 0) break;
cnt ++;
insert(str);
}
dfs(0);
return 0;
}
HDU 2846 Repository
题意：给定一些单词作为字典，和一些单词作为询问，对于每个询问，求出它在所有字典单词中作为单词子串出现的次数（它只能在同一单词中以子串形式出现一次）
对于每个字典中的单词，让它所有后缀都在字典树中建树，这样只要在字典树中找前缀就等同于找到子串了
需要注意的是，它只能在同一单词中以子串形式出现一次，如：str：dddddd 则ddd在str中只出现一次，所以对于同一单词产生的后缀，需要判重......
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
int n,q,root,cnt;
char str[22];
char keyword[22];
struct Trie {
int next[26];
int num;
int kind;
void init() {
memset(next,0,sizeof(next));
num = 0;
kind = -1;
}
} a[1111111];
void insert(char *key,int id,int kind) {
int p = root;
for(int i=id; key[i]; i++) {
int t = key[i] - 'a';
if(a[p].next[t] == 0) {
a[p].next[t] = ++cnt;
a[cnt].init();
}
p = a[p].next[t];
if(a[p].kind != kind) {
a[p].kind = kind;
a[p].num ++;
}
}
}
int query(char *key) {
int p = root;
int sum = 0;
for(int i=0; key[i]; i++) {
int t = key[i] - 'a';
if(a[p].next[t] == 0) return 0;
p = a[p].next[t];
}
sum += a[p].num;
return sum;
}
int main() {
root = 0;
cnt = 0;
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%s",str);
int len = strlen(str);
for(int j=0; j<len; j++)
insert(str,j,i);
}
scanf("%d",&q);
for(int i=0; i<q; i++) {
scanf("%s",keyword);
printf("%d
",query(keyword));
}
return 0;
}
POJ 1204 Word Puzzles
题意：给定了一个1000 * 1000 的由大写字母组成的矩阵，现在给出一些单词，要求在矩阵中找到每个单词，记录首字母的位置，以及它沿着什么方向走（8个方向，米字型）
将单词建立字典树，然后在矩阵中枚举每个点作为起点，8个方向直接找就行了..........
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
int n,m,w;
struct Word {
int x,y,dir,kind;
char word[1111];
}s[1111];
char str[1111][1111];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
int root , cnt ;
struct Trie {
int next[26];
int kind;
void init() {
memset(next,0,sizeof(next));
kind = -1;
}
}a[1111111];
void insert(char *key, int kind) {
int p = root;
for(int i=0; key[i]; i++) {
int t = key[i] - 'A';
if(a[p].next[t] == 0) {
a[p].next[t] = ++ cnt;
a[cnt].init();
}
p = a[p].next[t];
}
a[p].kind = kind;
}
void solve() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
int t = str[i][j] - 'A';
if(a[root].next[t] == 0) continue;
for(int k=0; k<8; k++) {
int p = a[root].next[t];
int x = i, y = j;
while(x >= 0 && x < n && y >= 0 && y < m && p) {
if(a[p].kind != -1) {
s[a[p].kind].dir = k;
s[a[p].kind].x = i;
s[a[p].kind].y = j;
}
x = x + dx[k];
y = y + dy[k];
int t = str[x][y] - 'A';
p = a[p].next[t];
}
}
}
}
for(int i=0; i<w; i++) {
printf("%d %d %c
",s[i].x,s[i].y,s[i].dir + 'A');
}
}
int main() {
while(scanf("%d%d%d",&n,&m,&w) != EOF) {
root = 0; cnt = 0;
for(int i=0; i<n; i++) scanf("%s",str[i]);
for(int i=0; i<w; i++) {
scanf("%s",s[i].word);
s[i].kind = i;
insert(s[i].word,i);
}
solve();
}
return 0;
}
待续.....