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 |
C++是wa,G++是AC,而且我的mark没用,但是删了就会超时,试试啊#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<string> #include<cmath> #include<vector> #include<list> #include<stack> #include<queue> #include<map> #include<set> #pragma comment(linker,"/STACK:102400000,102400000") #define lowbit(i) (i) & (-i) #define LL long long #define sqr(a) ((a)*(a)) #define MOD 1000000007 #define lson(step) step<<1 #define rson(step) step<<1|1 #define mem(a,b) memset(a,b,sizeof(a)) #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) using namespace std; const LL INF=9223372036854775807; const int M=100000+5; char Map[1000+5][1000+5]; int l,c,w; int dis[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; int da[1000+5][3],mark[1000+5]; char ss[1000+5][1000+5]; typedef struct node { node *next[26],*fail; int num; void init() { for(int i=0;i<26;i++) next[i]=NULL; fail=NULL; num=0; } }tree; tree *root; void insert(char s[],int num) { int l=strlen(s); tree *nownode=root; for(int i=0;i<l;i++) { if(nownode->next[s[i]-'A']==NULL) { nownode->next[s[i]-'A']=new tree; nownode->next[s[i]-'A']->init(); nownode=nownode->next[s[i]-'A']; } else nownode=nownode->next[s[i]-'A']; } nownode->num=num; } void getfail() { tree *son,*temp,*p=root; queue<tree *>q; q.push(p); while(!q.empty()) { temp=q.front(); q.pop(); for(int i=0;i<26;i++) { son=temp->next[i]; if(son!=NULL) { if(temp==root) son->fail=root; else { p=temp->fail; while(p) { if(p->next[i]) { son->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) son->fail=root; } q.push(son); } } } } int ok(int X,int Y) { if(X>=0&&Y>=0&&X<l&&Y<c) return 1; return 0; } void quetion(int NUM,int I,int ii,int X,int Y) { da[NUM][0]=X+(ii)*dis[I][0]-strlen(ss[NUM])*dis[I][0]; da[NUM][1]=Y+(ii)*dis[I][1]-strlen(ss[NUM])*dis[I][1]; da[NUM][2]=I; } void Query(char s[],int I,int X,int Y) { int l=strlen(s); tree *p=root,*temp; for(int i=0;i<l;i++) { while(p!=root&&!p->next[s[i]-'A']) p=p->fail; p=p->next[s[i]-'A']; if(!p) p=root; temp=p; while(temp!=root) { if(temp->num) { quetion(temp->num,I,i+1,X,Y); mark[temp->num]=1; } else break; temp=temp->fail; } } } void query(int X,int Y) { int l; char s[1000]; for(int i=0;i<8;i++) { int xx=X,yy=Y; l=0; while(ok(xx,yy)) { s[l++]=Map[xx][yy]; xx+=dis[i][0],yy+=dis[i][1]; } s[l]='\0'; Query(s,i,X,Y); } } int deal(tree* T) { int i; if(T==NULL) return 0; for(i=0;i<26;i++) { if(T->next[i]!=NULL) deal(T->next[i]); } free(T); return 0; } int main() { while(~scanf("%d%d%d",&l,&c,&w)) { memset(mark,0,sizeof(mark)); root=new tree; root->init(); for(int i=0;i<l;i++) scanf("%s",Map[i]); for(int i=1;i<=w;i++) { scanf("%s",ss[i]); insert(ss[i],i); } getfail(); for(int i=0;i<l;i++) { query(i,0); query(i,c-1); } for(int i=0;i<c;i++) { query(0,i); query(l-1,i); } for(int i=1;i<=w;i++) printf("%d %d %c\n",da[i][0],da[i][1],da[i][2]+'A'); deal(root); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator