| ||||||||||
| 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