#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define M 1024
#define queue_size M<<8 
char s[M][M];
char tmp[M];
int dir[][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; 
int l,c,w;
int len[M];
typedef struct node
{
       node* fail;
       node* next[26];
       int k;
       node(){
           fail=NULL;memset(next,0,sizeof(next));
       }
}Trie;
Trie* q[queue_size];
int head,tail;
struct result
{
       int x,y,d;
}ans[M];
void insert(char *str,Trie* rt,int k)
{
     int i=0,index;
     Trie* p=rt;
     while(str[i])
     {
          index=str[i]-'A';
          if(p->next[index]==NULL)p->next[index]=new Trie();
          p=p->next[index];
          i++;
     }
     p->k=k;
}
void build_ac_automation(Trie* rt)
{
     int i;
     head=tail=0;
     rt->fail=NULL;
     q[head++]=rt;
     while(head!=tail)
     {
          
          Trie *p=NULL,*tmp=q[tail++];tail%=queue_size;
          for(i=0;i<26;i++){
              if(tmp->next[i]!=NULL){
                  if(tmp==rt)tmp->next[i]->fail=rt;
                  else{
                      p=tmp->fail;
                      while(p!=NULL){
                          if(p->next[i]!=NULL){
                              tmp->next[i]->fail=p->next[i];
                              break;    
                          }
                          p=p->fail;
                      }
                      if(p==NULL)tmp->next[i]->fail=rt;
                  }
                  q[head++]=tmp->next[i];head%=queue_size;
              }
          }
          
     }
}
int legal(int x,int y)
{
    if(x<0||x>=l)return 0;
    if(y<0||y>=c)return 0;
    return 1;
}

void acrun(int x,int y,int d,node*r)  
{  
    int a;  
    Trie *tmp,*cur=r;  
      
    for(;legal(x,y);x+=dir[d][0],y+=dir[d][1]){  
        a=s[x][y]-'A';  
        while(!cur->next[a]&&cur!=r)  
            cur=cur->fail;  
        cur=cur->next[a];  
        if(cur==NULL) cur=r;  
        tmp=cur;  
  
        while(tmp!=r&&tmp->k!=-1){
           /* ans[tmp->k].x=x-dir[d][0]*(len[tmp->k]-1); 
            ans[tmp->k].y=y-dir[d][1]*(len[tmp->k]-1);  
            ans[tmp->k].d=d; */  
            tmp->k=-1;  
            tmp=tmp->fail; 
        }   
    }   
}  
void acwork(Trie* rt)
{
     int i;
     for(i=0;i<c;i++){
         acrun(0,i,3,rt);acrun(0,i,4,rt);acrun(0,i,5,rt);
         acrun(l-1,i,1,rt);acrun(l-1,i,0,rt);acrun(l-1,i,7,rt);
     }
     for(i=0;i<l;i++){
         acrun(i,0,1,rt);acrun(i,0,2,rt);acrun(i,0,3,rt);
         acrun(i,c-1,6,rt);acrun(i,c-1,7,rt);acrun(i,c-1,5,rt);
     }
     return;
     
}
int main()
{
    int i;
    scanf("%d%d%d",&l,&c,&w);
    for(i=0;i<l;i++)scanf("%s",s[i]);
    Trie* root=new Trie();
    for(i=1;i<=w;i++){
        scanf("%s",tmp);
        len[i]=strlen(tmp);
        insert(tmp,root,i);
    }
    build_ac_automation(root);

    acwork(root);
    for(i=1;i<=w;i++)
        printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].d+'A');
    //system("pause"); 
    return 0;
}

• 可能是你知道了一些不能知道的东西吧 (0) Yang_Ming 2017-01-28 20:55:11