POJ 1204 AC自动机的初步认识+模板题

来源：恒创科技编辑：恒创科技编辑部

2024-02-02 09:33:59

前一向在搞字典树就是为了搞AC自动机...AC自动机的用处..或者说最一般的用处就是给一个字典..找一篇文章中哪些单词出现过的一种较优的方法...而AC自动机的结构或者说方法简单的说就是字典树+KMP...首先将字典中的所有单词构造一颗字典树(我前面的文章有详细的介绍字典树..这里就不说了)...然后再类似KMP的方法来给每个点构造Fail指针..而在用AC自动机在文章中查找中的过程很类似KMP在一列字符串中查找单词有无出现过的过程...

AC自动机的步骤是:

1、构造字典树

2、对每个点构造Fail指针

3、遍历文章得到结果

第一步就是构造字典树...和一般的构造字典树除了在新加接点时要将其Fail指针先指向Head..其余的一模一样...没有难度...

第二步是关键..首先什么是Fail指针？类似KMP中的Fail指针...这里用一个图来表示一下..红色的线段代表的就是Fail指针

什么是Fail指针? 观察我这幅图可以发现...Fail指针是节点指向节点的..意义是可以向上找到相同的子结构..

有一个字典树的情况下如何构造Fail指针?..看这副图..如果要构造D的Fail指针...看其父亲B->Fail指向的上面一个B的孩子中有没有D..有的话就指向那个D..假如上面的B孩子里没有D呢？那又只能继续看上面B->Fail..结果B的Fail是NULL...也就是往上也找不到了...D->NULL也只能是NULL...我这里为了处理方便..将所有->Fail==NULL都指向最头的超级节点了...我程序中Built_AC_automation一段就是构造Fail指针..我觉得我写得也还简洁吧...

BFS来一层一层的往下更新Fail值...做完一层做下一层...我开始就是更新时用的是DFS结果WA了很久的郁闷....我也搜过不少其他人的代码...觉得他们的这一部分写得很长...我就用个队列来解决...代码量很少 ..也比较好理解吧..

Fail指针到底有什么用？..Fail指针的好处就是在扫描一个文章时..如果匹配失败..没必要每次从根开始从头找..而是可以跳到前面的某个点继续往下找...提高查找效率..

Fail指针如何用？.通过这棵树搜索时...若发现当前点的孩子中没有当前所判断的字符...就看当前点的Fail点的孩子有无...一直往上Fail直到找到一个点其孩子有所判断的字符或者说找到了根都找不到符合的...就只能说这个字符不属于任何一个单词..只能继续搜下一个字符...

再回到这道题....是再一个矩阵中查找单词...并且有8个方向.. 从这个矩阵四周的每个点开始.每个点.八个方向扫过去~~边扫边在树中查找...八个方向就定义一个二维数组~~存下八个方向的x,y的走势~~循环着做很方便的...

Program:

#include<iostream>
#include<queue>
#define judge (y<ny && y>=0 && x<nx && x>=0)
using namespace std;
struct node
{
    node *s[26],*fail;
    char c;
    int w;      
}*head,*p;
struct pp
{
    int y,x,len;
    char c;      
}outdata[1001];
int ny,nx,n,i,face,len,t[8][2]={{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1}};
char s[1001][1001],str[2001];
node *UpdateFail(node *p,int k)
{
    if (p->s[k]!=NULL) return p->s[k];
    else
    if (p==head) return p;
    else 
    return UpdateFail(p->fail,k);   
}
void built_trie(node *h,int k)
{  
    if (k==len)
    {
         h->w=i;
         return;
    }
    if (h->s[str[k]-'A']==NULL)   
    {
         p=new node; 
         p->w=0;
         p->c=str[k];
         for (int j=0;j<26;j++) p->s[j]=NULL; 
         p->fail=head;      
         h->s[str[k]-'A']=p;
    }     
    built_trie(h->s[str[k]-'A'],k+1);
    return;
}
queue< node* > myqueue;
void built_AC_automation()
{
    int i;
    node *h;
    while (!myqueue.empty()) myqueue.pop();
    myqueue.push(head);
    while (!myqueue.empty())
    {
         h=myqueue.front();
         myqueue.pop();  
         for (i=0;i<26;i++)
         if (h->s[i]!=NULL)  
         {
              myqueue.push(h->s[i]);               
              if (h==head) h->s[i]->fail=head;
              else                
              h->s[i]->fail=UpdateFail(h->fail,i);             
         }
    }
    return; 
}
void find(int y,int x,node *h)
{
    if (h==NULL) h=head;  
    if (h->w && outdata[h->w].x<0) 
    {
         outdata[h->w].x=x-t[face][0]*(outdata[h->w].len);
         outdata[h->w].y=y-t[face][1]*(outdata[h->w].len);
         outdata[h->w].c=face+'A';   
    }     
    if (!judge) return;
    while (h->s[s[y][x]-'A']==NULL && h!=head) h=h->fail; 
    find(y+t[face][1],x+t[face][0],h->s[s[y][x]-'A']);
    return;
}
int main()
{   
    memset(outdata,-1,sizeof(outdata)); 
    scanf("%d%d%d",&ny,&nx,&n);    
    getchar(); 
    for (i=0;i<ny;i++) scanf("%s",s[i]);
    head=new node;  
    head->w=0; 
    head->fail=head;
    for (i=0;i<26;i++) head->s[i]=NULL;
    for (i=1;i<=n;i++)
    {
         scanf("%s",str);
         len=strlen(str);
         outdata[i].len=len;
         built_trie(head,0);
    }
    built_AC_automation();
    for (face=0;face<8;face++)
    {
         for (i=0;i<nx;i++) {  find(0,i,head); find(ny-1,i,head); }
         for (i=0;i<ny;i++) {  find(i,0,head); find(i,nx-1,head); }
    }    
    for (i=1;i<=n;i++) printf("%d %d %c\n",outdata[i].y,outdata[i].x,outdata[i].c);
    return 0;   
}