首页 > 代码库 > 2017多校第6场 HDU 6096 String AC自动机
2017多校第6场 HDU 6096 String AC自动机
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6096
题意：给了一些模式串，然后再给出一些文本串的不想交的前后缀，问文本串在模式串的出现次数。
解法：
因为要求前缀后缀都包含的个数，所以可以把字符串a转换成a#a这样一个字符串，比如abca就转换成abca#abca
然后对于一组前缀a后缀b转换成b{a,比如ab ca,就是ca{ab，
然后对前缀后缀的串建立AC自动机，让主串去匹配，如上述例子，ca{ab满足为abca{abca的一个子串，也就是abca满足这个前缀后缀，所以问题，就转换成了典型的ac自动机匹配问题。
加个{的原因是为了只让后缀{前缀这种串能在AC自动机匹配到。
然后求答案的时候，需要对连接到自己的fail的位置累加一下，含义想一下就明白了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
const int maxs = 30;
string s[maxn];
int d[maxn],pos[maxn],ans[maxn],st[maxn],len[maxn];
struct Acautomata{
int nxt[maxn][maxs],cnt[maxn],fail[maxn],match[maxn],dep[maxn];
int L, root;
int newnode(){
for(int i=0; i<maxs; i++) nxt[L][i]=-1;
cnt[L++]=0;
fail[L-1]=0;
return L-1;
}
void init(){
L = 0;
root = newnode();
}
int Insert(string a){
int now=root;
for(int i=0; a[i]; i++){
if(nxt[now][a[i]-‘a‘]==-1){
nxt[now][a[i]-‘a‘]=newnode();
dep[L-1]=i+1;
}
now=nxt[now][a[i]-‘a‘];
}
cnt[now]=1;
return now;
}
void build()
{
queue<int>q;
int now=root;
fail[0] = 0;
for(int i=0; i<maxs; i++){
if(nxt[now][i]==-1){
nxt[now][i]=root;
continue;
}
else{
fail[nxt[now][i]]=root;
q.push(nxt[now][i]);
}
}
while(!q.empty())
{
now = q.front();
q.pop();
for(int i=0; i<maxs; i++){
if(nxt[now][i]!=-1){
q.push(nxt[now][i]);
fail[nxt[now][i]] = nxt[fail[now]][i];
match[nxt[now][i]] = cnt[nxt[now][i]]?nxt[now][i]:match[nxt[fail[now]][i]];
}else{
nxt[now][i] = nxt[fail[now]][i];
}
}
}
}
void solve1(string a, int h){
int now=root;
int sz = a.size();
for(int i=0; i<sz; i++){
now=nxt[now][a[i]-‘a‘];
while(dep[now]>h){
now=fail[now];
}
ans[match[now]]++;
}
}
void solve2(){//累加答案，对连到自己的fail进行累加求和
memset(d, 0, sizeof(d));
int j, k = 0;
for(int i=0; i<L; i++) d[fail[i]]++;
for(int i=0; i<L; i++) if(!d[i]) st[k++]=i;
for(int i=0; i<k; i++){
j=fail[st[i]];
ans[j]+=ans[st[i]];
if(!(--d[j])){
st[k++]=j;
}
}
}
}ZXY;
int n, q;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ZXY.init();
scanf("%d%d", &n,&q);
for(int i=0; i<n; i++){
cin>>s[i];
len[i] = s[i].size()+1;
string temp=s[i];
s[i]+=char(‘z‘+1);
s[i]+=temp;
}
for(int i=0; i<q; i++){
string s1,s2;
cin>>s1>>s2;
s2 = s2 + char(‘z‘+1);
s2 = s2 + s1;
pos[i] = ZXY.Insert(s2);
}
ZXY.build();
for(int i=0; i<n; i++){
ZXY.solve1(s[i],len[i]);
}
ZXY.solve2();
for(int i=0; i<q; i++) printf("%d\n", ans[pos[i]]);
for(int i=0; i<=ZXY.L; i++){
ans[i]=0;
ZXY.match[i]=0;
}
}
return 0;
}
2017多校第6场 HDU 6096 String AC自动机
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。