AC自动机

初步学了下，一些优化还没学会，做了一道模板题和两道变式，最后一道想尽办法优化还是有4个测试点超时…先贴上来吧，回头想办法。
简单版

就纯粹套模板

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int tree[MAX_N][30];
int color[MAX_N];
int cnt=1;
int fail[MAX_N];
void build(string s)
{
   
    int root=0;
    int i;
    for(i=0;i<s.size();i++)
    {
   
        int x=s[i]-'a';
        if(!tree[root][x])
        {
   
            tree[root][x]=cnt++;
        }
        root=tree[root][x];
    }
    color[root]++;
}
void buildfail()
{
   
    int root=0;
    queue<int>q;
    int i;
    for(i=0;i<26;i++)
    {
   
        if(tree[root][i])
        {
   
            fail[tree[root][i]]=0;
            q.push(tree[root][i]);
        }
    }
    while(!q.empty())
    {
   
        int now=q.front();
        q.pop();
        for(i=0;i<26;i++)
        {
   
            if(tree[now][i])
            {
   
                fail[tree[now][i]]=tree[fail[now]][i];
                q.push(tree[now][i]);
            }
            else
            {
   
                tree[now][i]=tree[fail[now]][i];
            }
        }
    }
}
int Find(string s)
{
   
    int now=0;
    int ans=0;
    int i;
    for(i=0;i<s.size();i++)
    {
   
        now=tree[now][s[i]-'a'];
        for(int j=now;j&&color[j]!=-1;j=fail[j])
        {
   
            ans+=color[j];
            color[j]=-1;
        }
    }
    return ans;
}
int main()
{
   
    int n;
    cin>>n;
    string s;
    while(n--)
    {
   

        cin>>s;
        build(s);
    }
    buildfail();
    cin>>s;
    int ans=Find(s);
    cout<<ans<<endl;
}

加强版
这题有个小小的变式，因为是要找出每个字符串的出现次数，所以这里不需要color数组了，把每个字符串末尾的节点标记上相应字符串的编号，最后查询的时候每经过这个节点，就把其对应的字符串编号加一，代表出现了一次，最后直接遍历字符串找最大就行。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=1000000+5;
const int INF=0x7fffffff;
const int inf=100000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
int tree[MAX_N][30];
int e[MAX_N];
int cnt=1;
int fail[MAX_N];
int ans[155];
string s[155];
string c;
void build(string s,int num)
{
   
    int root=0;
    int i;
    for(i=0; i<s.size(); i++)
    {
   
        int x=s[i]-'a';
        if(!tree[root][x])
        {
   
            tree[root][x]=cnt++;
        }
        root=tree[root][x];
    }
    e[root]=num;
}
void buildfail()
{
   
    int root=0;
    queue<int>q;
    int i;
    for(i=0; i<26; i++)
    {
   
        if(tree[root][i])
        {
   
            fail[tree[root][i]]=0;
            q.push(tree[root][i]);
        }
    }
    while(!q.empty())
    {
   
        int now=q.front();
        q.pop();
        for(i=0; i<26; i++)
        {
   
            if(tree[now][i])
            {
   
                fail[tree[now][i]]=tree[fail[now]][i];
                q.push(tree[now][i]);
            }
            else
            {
   
                tree[now][i]=tree[fail[now]][i];
            }
        }
    }
}
void Find(string s)
{
   
    int now=0;
    int i;
    for(i=0; i<s.size(); i++)
    {
   
        now=tree[now][s[i]-'a'];
        for(int j=now; j; j=fail[j])
        {
   
            int u=e[j];
            ans[u]++;
        }
    }
    return;
}
int main()
{
   
    int n;
    INIT();
    while(cin>>n&&n)
    {
   
        me(tree,0);
        me(e,0);
        me(fail,0);
        me(ans,0);
        int i;
        for(i=1; i<=n; i++)
        {
   
            cin>>s[i];
            build(s[i],i);
        }
        buildfail();
        cin>>c;
        Find(c);
        int mx=0;
        for(i=1;i<=n;i++)
        {
   
            mx=max(mx,ans[i]);
        }
        cout<<mx<<endl;
        for(i=1;i<=n;i++)
        {
   
            if(ans[i]==mx)
                cout<<s[i]<<endl;
        }

    }

}

二次加强
这题题意和上面一题没什么区别，就是不用求最大，把所有字符串出现次数输出就行，但是这题用同样的方法时间复杂度过不去，我是认为问题出在fail[]上，因为每次查询的时候都是暴力跳fail，而在跳的过程中很有可能所对应的节点不是字符串末端，所以会浪费复杂度，因此我前面加了个g[]，在创造fail的时候直接判断下一个是不是末端，是的话g[i]=fail[i]，不是就g[i]=g[fail[i]]，这样查询的时候直接跳g就行了，然而，还是有几个点过不去…

AC自动机

全站热榜