AC自动机

定义：

   $Aho–Corasick$Aho–Corasick 算法是由 $AlfredV.Aho$AlfredV.Aho 和 $MargaretJ.Corasick$MargaretJ.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa），算法的时间复杂度会近似于匹配的二次函数。
  该算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设 $Trie$Trie 树的单词 $cat$cat匹配失败，但是在 $Trie$Trie 树中存在另一个单词 $cart$cart，失配指针就会指向前缀 $ca$ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。
【以上来自维基百科】
总的来说：
$AC$AC 自动机是 以 $TRIE$TRIE 的结构为基础 ，结合 $KMP$KMP 的思想建立的。
$AC$AC 自动机在做匹配时，同一位上可匹配多个模式串。

前置技能：

$\text{trie（字典树），KMP}$trie（字典树），KMP
KMP 用于单模式串匹配，而 $AC$AC 自动机用于多模式串匹配。

复杂度：

$O\left(n\right)$O(n)（ $n$n:文本串的长度）

建立一个 $AC$AC 自动机的步骤：

(1).基础的 $TRIE$TRIE 结构：将所有的模式串构成一棵字典树 。
(2). $KMP$KMP 的思想：对字典树上所有的结点构造失配指针 $fail$fail。

相关定义：

1.失配指针：

  即 $fail$fail 指针，其作用相当于 $KMP$KMP 算法中的 $next$next 数组的作用。
   $next$next 指针求的是最长的公共真前后缀长度，而 $fail$fail 指向所有模式串的前缀中匹配当前状态的最长后缀。
详解

模板：

Keywords Search HDU - 2222：
给出 $n$n 个模式串， $1$1 个文本串，问文本串中出现了几个模式串？
（存个模板，附加理解）

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char key[N][55];
char text[N];
int trie[N][26],fail[N],word[N];//字典树，fail指针指向，字典树中每个节点
int cnt;
queue<int>que;
void build(char s[])//建立字典树
{
    int len=strlen(s);
    int p=0;
    for(int i=0;i<len;i++)
    {
        int t=s[i]-'a';
        if(trie[p][t]==0)
            trie[p][t]=++cnt;
        p=trie[p][t];
    }
    word[p]++;//
}
void bfs()//建立fail指针
{
    while(!que.empty())
        que.pop();
    for(int i=0;i<26;i++)
    {
        if(trie[0][i])
        {
            fail[trie[0][i]]=0;
            que.push(trie[0][i]);
        }
    }
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<26;i++)
        {
            if(trie[now][i])//指向其父亲的fail指针的这个节点(i)
            {
                fail[trie[now][i]]=trie[fail[now]][i];
                que.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点(不存在)指向当前节点的fail指针的这个子节点
                trie[now][i]=trie[fail[now]][i];//修改了字典树的结构，可以使匹配转移加完善
        }
    }
}
int query(char ss[])//对文本串进行查询
{
    int len=strlen(ss);
    int ans=0,p=0;
    for(int i=0;i<len;i++)
    {
        p=trie[p][ss[i]-'a'];
        for(int j=p;j&&word[j]!=-1;j=fail[j])
        {//一直向下寻找，直到匹配失败（失败指针指向根或者当前节点已经找过）
            ans+=word[j];
            word[j]=-1;//把遍历过的节点标记，否则重复计算
        }
    }
    return ans;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        memset(trie,0,sizeof(trie));
        memset(word,0,sizeof(word));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%s",key[i]);
        for(int i=1;i<=n;i++)
            build(key[i]);
        bfs();
        scanf("%s",text);
        printf("%d\n",query(text));
    }
    return 0;
}

病毒侵袭 HDU - 2896
多个文本串，多个模式串，要求记录每个文本串中出现了哪些模式串。
在查询是不能简单把 $word$word 数组赋值-1，可以用标记数组代替。

#include <bits/stdc++.h>//不能用cin
using namespace std;
const int N=6e4+5;
char ss[10010];
int trie[N][100],fail[N],word[N];//ASCII码中可见字符33~126
bool vis[N];
queue<int>que;
vector<int>web[1010];
int cnt;
void build(char s[],int m)
{
    int p=0,len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int t=s[i]-' ';
        if(trie[p][t]==0)
            trie[p][t]=++cnt;
        p=trie[p][t];
    }
    word[p]=m;
}
void bfs()
{
    while(!que.empty())
        que.pop();
    for(int i=0;i<95;i++)
    {
        if(trie[0][i])
        {
            fail[i]=0;
            que.push(trie[0][i]);
        }
    }
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<95;i++)
        {
            if(trie[now][i])
            {
                fail[trie[now][i]]=trie[fail[now]][i];
                que.push(trie[now][i]);
            }
            else
                trie[now][i]=trie[fail[now]][i];
        }
    }
}
void query(char s[],int m)
{
    int p=0,len=strlen(s);
    for(int i=0;i<len;i++)
    {
        p=trie[p][s[i]-' '];
        for(int j=p;j&&!vis[j];j=fail[j])
        {
            if(word[j]>0)
                web[m].push_back(word[j]);
            vis[j]=1;
        }
    }
}
int main()
{
    //std::ios::sync_with_stdio(false);
    int n,m;
    cnt=0;
    scanf("%d",&n);
    getchar();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ss);
        build(ss,i);
    }
    bfs();
    scanf("%d",&m);
    int ans=0;
    getchar();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ss);
        //getline(cin,ss);
        fill(vis,vis+cnt+1,false);
        query(ss,i);
        if(web[i].size())
            ans++;
    }
    for(int i=1;i<=m;i++)
    {
        if(web[i].size())
        {
            printf("web %d:",i);
            sort(web[i].begin(),web[i].end());
            for(int j=0;j<web[i].size();j++)
                printf(" %d",web[i][j]);
            printf("\n");
        }
    }
    printf("total: %d\n",ans);
    return 0;
}

Detect the Virus ZOJ - 3430
问题还是和上面一样，多个模式串，多个文本串，求个数。
恶心的是要对每个字符串进行反编码，而且字符的范围是0~256，所以反编码后的数组不能用 $char$char ,用 $int$int 保存。而且题目不太好懂。

#include <bits/stdc++.h>
using namespace std;
const int N=513*64;
char ss[N];
int r[N];
int cnt,x,trie[N][256],word[N],fail[N],num[N];
bool vis[N];
queue<int>que;
void change(char s[])
{
    int len=strlen(s),i,cot=0;
    x=0;
    for(i=0;i<len&&s[i]!='=';i++)
    {
        int t;
        if(s[i]>='a'&&s[i]<='z')
            t=s[i]-'a'+26;
        else if(s[i]>='A'&&s[i]<='Z')
            t=s[i]-'A';
        else if(s[i]>='0'&&s[i]<='9')
            t=s[i]-'0'+52;
        else if(s[i]=='+')
            t=62;
        else if(s[i]=='/')
            t=63;
        for(int j=6;j>0;j--)
        {
            num[j+cot]=t%2;
            t/=2;
        }
        cot+=6;
    }
    if(i==len-1)//'=':3k+2
        cot-=2;
    else if(i==len-2)//'==':3k+1
        cot-=4;
    for(int i=1;i<=cot;i++)
    {
        int t=0;
        for(int j=i;j<=i+7;j++)
            t+=(1<<(7-j+i))*num[j];
        r[x++]=t;
        i+=7;
    }
}
void build(int s[],int len)
{
    int p=0;
    for(int i=0;i<len;i++)
    {
        int t=s[i];
        if(trie[p][t]==0)
            trie[p][t]=++cnt;
        p=trie[p][t];
    }
    word[p]++;
}
void bfs()
{
    while(!que.empty())
        que.pop();
    for(int i=0;i<256;i++)
    {
        if(trie[0][i])
        {
            fail[trie[0][i]]=0;
            que.push(trie[0][i]);
        }
    }
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<256;i++)
        {
            if(trie[now][i])
            {
                fail[trie[now][i]]=trie[fail[now]][i];
                que.push(trie[now][i]);
            }
            else
                trie[now][i]=trie[fail[now]][i];
        }
    }

}
int query(int s[],int len)
{
    int p=0,ans=0;
    fill(vis,vis+cnt+1,false);
    for(int i=0;i<len;i++)
    {
        p=trie[p][s[i]];
        for(int j=p;j&&!vis[j];j=fail[j])
        {
            ans+=word[j];
            vis[j]=1;
        }
    }
    return ans;
}
int main()
{
    int n,m,y=0;
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        memset(word,0,sizeof(word));
        memset(trie,0,sizeof(trie));
        for(int i=1;i<=n;i++)
        {
            scanf("%s",ss);
            change(ss);
            build(r,x);
        }
        bfs();
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%s",ss);
            change(ss);
            printf("%d\n",query(r,x));
        }
        printf("\n");
    }
    return 0;
}

病毒侵袭持续中 HDU - 3065
求出现的模式串每个的出现次数。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+100;
const int maxn=2e6+6;
char vir[1010][60],ss[maxn];
int trie[N][95],fail[N],word[N],cnt,num[1010];
set<int>st;
queue<int>que;
void build(char s[],int m)
{
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++)
    {
        int t=s[i]-' ';
        if(trie[p][t]==0)
            trie[p][t]=++cnt;
        p=trie[p][t];
    }
    word[p]=m;
}
void bfs()
{
    while(!que.empty())
        que.pop();
    for(int i=0;i<95;i++)
    {
        if(trie[0][i])
        {
            fail[trie[0][i]]=0;
            que.push(trie[0][i]);
        }
    }
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=0;i<95;i++)
        {
            if(trie[u][i])
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                que.push(trie[u][i]);
            }
            else
                trie[u][i]=trie[fail[u]][i];
        }
    }
}
void query(char s[])
{
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++)
    {
        p=trie[p][s[i]-' '];
        for(int j=p;j;j=fail[j])
        {
            if(word[j]>0)
            {
                num[word[j]]++;
                st.insert(word[j]);
            }
        }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        memset(trie,0,sizeof(trie));
        memset(word,0,sizeof(word));
        fill(num,num+1+n,0);
        st.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",vir[i]);
            build(vir[i],i);
        }
        bfs();
        scanf("%s",ss);
        query(ss);
        set<int>::iterator it;
        for(it=st.begin();it!=st.end();it++)
            printf("%s: %d\n",vir[*it],num[*it]);
    }
    return 0;
}