| input | output |
|---|---|
5 kare 10 kanojo 20 karetachi 1 korosu 7 sakura 3 3 k ka kar |
kanojo kare korosu karetachi kanojo kare karetachi kare karetachi
|
分析：若对每个询问走一遍字典树是超时的；
对于询问建立字典树，然后将排好序的单词依次插入就得到了答案；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define Lson L, mid, rt<<1 #define Rson mid+1, R, rt<<1|1 const int maxn=1e6+10; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} int n,m,k,t,q[maxn],to[maxn],id; bool flag; char ans[15001][11][21]; struct node { char b[21]; int num; bool operator<(const node&p)const { if(num==p.num)return strcmp(b,p.b)<0; else return num>p.num; } }a[maxn]; struct node1 { int nxt[26],num; }b[maxn]; char c[21]; void add(char*c,int tot) { int now=0; for(int i=0;c[i];i++) { int x=c[i]-‘a‘; if(!b[now].nxt[x])b[now].nxt[x]=++id; now=b[now].nxt[x]; } if(!b[now].num)b[now].num=tot,to[tot]=tot; else to[tot]=b[now].num; } void gao(char*c) { int now=0; for(int i=0;c[i];i++) { int x=c[i]-‘a‘; if(b[now].nxt[x]) { int y=b[now].nxt[x]; if(b[y].num&&q[b[y].num]<=9) { strcpy(ans[b[y].num][q[b[y].num]++],c); } now=b[now].nxt[x]; } else break; } } int main() { int i,j; scanf("%d",&n); rep(i,1,n)scanf("%s %d",a[i].b,&a[i].num); sort(a+1,a+n+1); scanf("%d",&m); rep(i,1,m)scanf("%s",c),add(c,i); rep(i,1,n)gao(a[i].b); rep(i,1,m) { if(flag)printf("\n");else flag=true; rep(j,0,q[to[i]]-1)printf("%s\n",ans[to[i]][j]); } //system("Pause"); return 0; }
原文：http://www.cnblogs.com/dyzll/p/5855052.html