[USACO][Section 2.3][AC自动机] The Longest Prefix

题目大意

---

思路

---

代码

---

/*
ID: lujunda1
LANG: C++
PROG: prefix
*/
#include
#include
#include
using namespace std;

#define T_SIZE 200000
#define P_SIZE 10
#define TOTAL_P 200

struct trie
//利用结构体来封装字典树的节点。
{
    trie* next[26];
    trie* fail;
    bool tail;
    //判断当前节点是否为某个单词的结尾。
    int len; 
    //节点在字典树中的“深度”。 
    trie()
    //构造函数。
    {
        for(int i=0;i<26;i++)
            next[i]=NULL;
        fail=NULL;
        tail=false;
        len=0;
    }
};

char T[T_SIZE+1];
char P[P_SIZE+1];
trie* q[TOTAL_P*P_SIZE];
int T_len[T_SIZE+1];
//T_len用于本题，记录连续区间。
//例：“T_len[i]==x”表示以T[i]为首匹配的单词的最大长度为x。 

void insert(trie* root,char* s)
//将字符串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->next[s[i]-'A']->len=p->len+1;
        }
        p=p->next[s[i]-'A'];
    }
    p->tail=true;
}

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];
            }
    }
}

void ac_find(trie* root,char* T)
{
    memset(T_len,0,sizeof(T_len));
    trie* p=root;
    for(int i=0,len=strlen(T);inext[T[i]-'A']==NULL&&p!=root)
        //若当前节点的没有一个字符为T[i]的儿子且当前节点不是根节点
        //通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。 
            p=p->fail;
        if(p->next[T[i]-'A']!=NULL)
        //p->next[T[i]-'A']==NULL说明没找到合适的节点，p指针指在根节点上。
            p=p->next[T[i]-'A']; 
        trie* temp=p;
        while(temp!=root)
        //顺着失败指针往回走，一直到根节点。 
            if(temp->tail)
            {
                if(T_len[i-(temp->len-1)]len)
                    T_len[i-(temp->len-1)]=temp->len;
                break;
            }
            else
                temp=temp->fail;
    }
}

int solved()
{
    int len=strlen(T),pos=-1;
    //pos表示最长连续区间在T中的结尾位置。 
    for(int i=0;i<=pos+1&&ipos)
            pos=T_len[i]+i-1;
    return pos+1;
}

int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    trie* root=new trie;
    while(scanf("%s",P)&&strcmp(P,"."))
        insert(root,P);
    build_ac_automation(root);
    T[0]='\0';
    while(~scanf("%s",T+strlen(T)));
    ac_find(root,T);
    printf("%d\n",solved());
}