卢俊达

题目大意

思路

代码

#include<iostream>
#include<stdio.h>
using namespace std;

#define MAP_SIZE 1000
#define P_SIZE 1000
#define TOTAL_P 1000

struct trie
//利用结构体来封装字典树的节点。
{
	trie* next[26];
	trie* fail;
	int num;
	int len;
	trie()
	//构造函数。
	{
		for(int i=0;i<26;i++)
			next[i]=NULL;
		fail=NULL;
		len=0;
		num=0;
	}
};

struct point
{
	int x;
	int y;
	char dir;
};

char P[P_SIZE+1];
char map[MAP_SIZE+1][MAP_SIZE+1];
trie* q[TOTAL_P*P_SIZE];
point res[TOTAL_P];
int L,C,W;

void insert(trie* root,char* s,int num)
//将字符串s所表示的单词插入到字典树中。
{
	trie* p=root;
	for(int i=0;s[i]!='\0';i++)
	{
		if(p->next[s[i]-'A']==NULL)
			p->next[s[i]-'A']=new trie;
		p=p->next[s[i]-'A'];
	}
	p->num=num;
	p->len=strlen(s);
}

void  build_ac_automation(trie* root)
//利用广搜构建失败指针 
{
	int head=0,tail=0;
	q[tail++]=root;
	while(head!=tail)
	{
		trie* front=q[head++];
		//front为队头元素 
		for(int i=0;i<26;i++)
			if(front->next[i]!=NULL)
			//遍历队头元素的子节点 
			{
				trie* p=front->fail;
				while(p!=NULL)
				//只有根节点的失败指针为NULL 
				{
					if(p->next[i]!=NULL)
					//顺着失败指针往回走，直至某个节点，其拥有一个字母为'A'+i的子节点。 
					{
						front->next[i]->fail=p->next[i];
						break;
					}
					p=p->fail;
				}
				if(p==NULL)
				//p==NULL说明顺着失败指针往回走的过程中没有找到合适的节点，所以将失败指针指向根节点。 
					front->next[i]->fail=root;
				q[tail++]=front->next[i];
			}
	}
}

bool range(int i,int j)
//判断坐标（i，j）是否在字谜矩阵范围内。 
{
	return i>=0&&j>=0&&i<L&&j<C?true:false;
}

int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
void ac_find(trie* root,int i,int j,int d)
//用以（i，j）为起点，向d方向伸展的字符串作为被匹配串，并与模式串进行匹配。 
{
	trie* p=root;
	for(;range(i,j);i+=dir[d][0],j+=dir[d][1])
	{
		while(p->next[map[i][j]-'A']==NULL&&p!=root)
		//若当前节点的没有一个字符为map[i][j]的儿子且当前节点不是根节点
		//通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。 
			p=p->fail;
		if(p->next[map[i][j]-'A']!=NULL)
		//p->next[map[i][j]-'A']==NULL说明没找到合适的节点，p指针指在根节点上。
			p=p->next[map[i][j]-'A']; 
		trie* temp=p;
		while(temp!=root&&temp->num!=-1)
		//顺着失败指针往回走，一直到根节点。 
		{
			if(temp->len!=0)
			{
				res[temp->num].x=i-dir[d][0]*(temp->len-1);
				res[temp->num].y=j-dir[d][1]*(temp->len-1);
				res[temp->num].dir='A'+d;
			}
			temp->num=-1;
			//标记num为-1，避免重复计算。 
			temp=temp->fail;
		}
	}
}

int main()
{
	trie* root=new trie;
	scanf("%d%d%d",&L,&C,&W);
	getchar();
	for(int i=0;i<L;i++)
		gets(map[i]);
	for(int i=0;i<W;i++)
	{
		gets(P);
		insert(root,P,i);
	}
	build_ac_automation(root);
	for(int i=0;i<L;i++)
	//以字谜矩阵的左右两条边上的点为起点向三个方向伸展的字符串作被匹配串。 
	{
		ac_find(root,i,C-1,5);
		ac_find(root,i,C-1,6);
		ac_find(root,i,C-1,7);
		ac_find(root,i,0,1);
		ac_find(root,i,0,2);
		ac_find(root,i,0,3);
	}
	for(int i=0;i<C;i++)
	//同理，遍历上下两条边。 
	{
		ac_find(root,L-1,i,0);
		ac_find(root,L-1,i,1);
		ac_find(root,L-1,i,7);
		ac_find(root,0,i,3);
		ac_find(root,0,i,4);
		ac_find(root,0,i,5);
	}
	for(int i=0;i<W;i++)
		printf("%d %d %c\n",res[i].x,res[i].y,res[i].dir);
}