几道字典树题目
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;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\n",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;}待续.....