| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
32ms,有什么地方可以优化吗?请大牛们帮忙看看~~谢谢了~~#include<iostream> #define N 100005 #define br 26 using namespace std; int end[1005]; struct Trie{ int cnt;//记录有多少个经过这个节点的字符串。 int next[br]; void init() { int i; cnt=0; for(i=0;i<br;i++) next[i]=0; } }tree[N]; int root=0,num=0,cid=0; void insert(char* s) { int rt=root; while(*s) { int t=*s-'a'; if(tree[rt].next[t]==0) { num++; tree[num].init(); tree[rt].next[t]=num; } rt=tree[rt].next[t]; tree[rt].cnt++; s++; } } void find(char* s,int i) { int rt=root; int len=0; while(*s) { len++; int t=*s-'a'; rt=tree[rt].next[t]; if(tree[rt].cnt==1) { printf("%c\n",*s); s++; while(*s) { t=*s-'a'; rt=tree[rt].next[t]; tree[rt].cnt=0; s++; } return; } if(len==end[i]) { printf("%c\n",*s); return; } printf("%c",*s); s++; } } char str[1005][30]; int main() { int cnt,i=0; while(scanf("%s",&str[i])!=EOF) { end[i]=strlen(str[i]); insert(str[i++]); } cnt=i; for(i=0;i<cnt;i++) { printf("%s ",str[i]); find(str[i],i); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator