Source Code

Problem: 1204  User: yzhw 
Memory: 7520K  Time: 3907MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
# include <queue>
using namespace std;
struct node
{
	vector<node> next;
	char ch;
	int end;
    int level;
	node  *pre;
	int search(char pos)
	{
		int s=0,e=next.size()-1,mid=(s+e)/2;
		while(s<=e)
		{
			mid=(s+e)/2;
			if(next[mid].ch==pos) return mid;
			else if(pos>next[mid].ch) s=mid+1;
			else e=mid-1;
		}
		return -1;
	}
};
struct ansnode
{
	char str[1024];
	int r,c,dir;
}l[1001];
int n,r,c;
class dic
{
public:
	node head;
	dic()
	{
		head.pre=&head;
		head.end=0;
		head.level=0;
	}
    void insert(char *ori,node &pos,int level=0)
	{
		pos.level=level;
		if((*ori)=='\0') 
		{
			pos.end++;
			return;
		}
		int p=pos.search(*ori);
		if(p!=-1)
		{
			insert(ori+1,pos.next[p],level+1);
		}
		else
		{
			vector<node>::iterator it;
			for(it=pos.next.begin();it!=pos.next.end()&&it->ch<(*ori);it++);
			node tmp;
			tmp.ch=(*ori);
			tmp.pre=NULL;
			tmp.end=0;
			pos.next.insert(it,tmp);
			insert(ori+1,pos.next[pos.search(*ori)],level+1);
		}
	}
	void makepre()
	{
	    queue<node*> l1,l2;
		l1.push(&head);
		l2.push(&head);
		while(!l1.empty())
		{
			node *p=l1.front(),*fa=l2.front();
			l1.pop();
			l2.pop();
			if(fa==&head)
				p->pre=&head;
			else
			{
				fa=fa->pre;
				while(fa!=&head&&fa->search(p->ch)==-1)
				   fa=fa->pre;
				if(fa->search(p->ch)!=-1)
					p->pre=&(fa->next[fa->search(p->ch)]);
				else
					p->pre=&head;

			}
			for(int i=0;i<p->next.size();i++)
			{
				l1.push(&(p->next[i]));
				l2.push(p);
			}
		}
	}
	void search(char *str,int dir,int x,int y)
	{
		int len=strlen(str);
		node *s=&head;
		for(int i=0;i<=len;)
		{
			if(s->end)
			{
				bool flag=true;
                char tmp=str[i];
				str[i]='\0';
				for(int j=1;j<=n;j++)
					if(l[j].dir==-1&&strcmp(str+i-s->level,l[j].str)==0)
					{
						(s->end)--; 
						if(dir==1)//down-up
						 {
							 l[j].dir=dir;
							 l[j].c=y;
							 l[j].r=x-(i-s->level);
						 }
						 else if(dir==2)//downleft-upright
						 {
							 l[j].dir=dir;
							 l[j].r=x-(i-s->level);
							 l[j].c=y+(i-s->level);
						 }
						 else if(dir==3)//left-right
						 {
							 l[j].dir=dir;
							 l[j].r=x;
							 l[j].c=y+i-s->level;
						 }
						 else if(dir==4)//upleft-downright
						 {
							 l[j].r=x+(i-s->level);
							 l[j].c=y+(i-s->level);
							 l[j].dir=dir;
						 }
						     
						 else if(dir==5)//up-down
						 {
							 l[j].dir=dir;
							 l[j].c=y;
							 l[j].r=x+(i-s->level);
						 }
						 else if(dir==6)//upright-downleft
						 {
							 l[j].dir=dir;
							  l[j].r=x+(i-s->level);
							 l[j].c=y-(i-s->level);
						 }
						 else if(dir==7)//right-left
						 {
							 l[j].r=x;
							 l[j].dir=dir;
							 l[j].c=y-(i-s->level);
						 }
						 else//rightdown-upleft
						 {
							 l[j].dir=dir;
							  l[j].r=x-(i-s->level);
							 l[j].c=y-(i-s->level);
						 }

					}
				str[i]=tmp;
			}
			if(s->search(str[i])!=-1)
			{
				s=&(s->next[s->search(str[i])]);
				i++;
			}
			else
			{
                if(s==&head)
					 i++;
				else
					s=s->pre;
				
			}
		}
		
	}

};
char map[1001][1001];
dic data;
int main()
{
	
	scanf("%d %d %d",&r,&c,&n);
	for(int i=0;i<r;i++)
		scanf("%s",map[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",l[i].str);
		l[i].dir=-1;
		data.insert(l[i].str,data.head);
	}
	data.makepre();	
	for(int i=0;i<c;i++)
	{
		char tmp[1024];
		memset(tmp,'\0',sizeof(tmp));
		for(int j=0;j<r;j++)
			tmp[j]=map[r-1-j][i];
		data.search(tmp,1,r-1,i);
	}
	for(int i=0;i<r;i++)
		data.search(map[i],3,i,0);
	for(int i=0;i<r;i++)
	{
		char tmp[1024];
		memset(tmp,'\0',sizeof(tmp));
		for(int j=0;j<c;j++)
			tmp[j]=map[i][c-1-j];
		data.search(tmp,7,i,c-1);
	}

    for(int i=0;i<c;i++)
	{
		char tmp[1024];
		memset(tmp,'\0',sizeof(tmp));
		for(int j=0;j<r;j++)
			tmp[j]=map[j][i];
		data.search(tmp,5,0,i);
	}
	
	for(int i=0;i<r;i++)
		
		{
            int j=0;
			char tmp[1024];
			memset(tmp,'\0',sizeof(tmp));
			for(int k=0;i+k<r&&j+k<c;k++)
				tmp[k]=map[i+k][j+k];
			data.search(tmp,4,i,j);
			int len=strlen(tmp);
			for(int k=0;k<len/2;k++)
			{
				char temp=tmp[k];
				tmp[k]=tmp[len-1-k];
				tmp[len-1-k]=temp;
			}
			data.search(tmp,8,i+len-1,j+len-1);
		}
	for(int j=0;j<c;j++)
		
		{
            int i=0;
			char tmp[1024];
			memset(tmp,'\0',sizeof(tmp));
			for(int k=0;i+k<r&&j+k<c;k++)
				tmp[k]=map[i+k][j+k];
			data.search(tmp,4,i,j);
			int len=strlen(tmp);
			for(int k=0;k<len/2;k++)
			{
				char temp=tmp[k];
				tmp[k]=tmp[len-1-k];
				tmp[len-1-k]=temp;
			}
			data.search(tmp,8,i+len-1,j+len-1);
		}
	for(int i=0;i<r;i++)
		
		{
            int j=0;
			char tmp[1024];
			memset(tmp,'\0',sizeof(tmp));
			for(int k=0;i-k>=0&&j+k<c;k++)
				tmp[k]=map[i-k][j+k];
			data.search(tmp,2,i,j);
			int len=strlen(tmp);
			for(int k=0;k<len/2;k++)
			{
				char temp=tmp[k];
				tmp[k]=tmp[len-1-k];
				tmp[len-1-k]=temp;
			}
			data.search(tmp,6,i-len+1,j+len-1);
		}
	for(int j=0;j<c;j++)
		
		{
            int i=r-1;
			char tmp[1024];
			memset(tmp,'\0',sizeof(tmp));
			for(int k=0;i-k>=0&&j+k<c;k++)
				tmp[k]=map[i-k][j+k];
			data.search(tmp,2,i,j);
			int len=strlen(tmp);
			for(int k=0;k<len/2;k++)
			{
				char temp=tmp[k];
				tmp[k]=tmp[len-1-k];
				tmp[len-1-k]=temp;
			}
			data.search(tmp,6,i-len+1,j+len-1);
		}
	for(int i=1;i<=n;i++)
		printf("%d %d %c\n",l[i].r,l[i].c,l[i].dir+64);
	//system("pause");
	return 0;
}