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就行了，然而，还是有几个点过不去…
#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=2000000+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];
vector<int>e[MAX_N];
int cnt=1;
int fail[MAX_N];
int g[MAX_N];
int ans[200005];
string s;
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].pb(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];
int u=tree[fail[now]][i];
if(e[u].size())
g[tree[now][i]]=u;
else
g[tree[now][i]]=g[u];
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=g[j])
{
for(int u=0;u<e[j].size();u++)
{
//cout<<e[j][u]<<endl;
ans[e[j][u]]++;
}
}
}
return;
}
int main()
{
int n;
INIT();
cin>>n;
int i;
for(i=1; i<=n; i++)
{
cin>>s;
build(s,i);
}
buildfail();
cin>>c;
Find(c);
for(i=1; i<=n; i++)
{
cout<<ans[i]<<endl;
}
}
查看8道真题和解析
