转自kuangbin的AC自动机（赛前最后一博）
2024-09-04 04:25:09
有了KMP和Trie的基础，就可以学习神奇的AC自动机了。AC自动机其实就是在Trie树上实现KMP，可以完成多模式串的匹配。
AC自动机 其实 就是创建了一个状态的转移图，思想很重要。
推荐的学习链接:
http://acm.uestc.edu.cn/bbs/read.php?tid=4294
http://blog.csdn.net/niushuai666/article/details/7002823
http://hi.baidu.com/nialv7/item/ce1ce015d44a6ba7feded52d
AC自动机专题训练链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25605#overview 这里我提交的代码是公开的，可以看到
题目来源：http://www.notonlysuccess.com/index.php/aho-corasick-automaton/
写AC自动机的代码风格是向昀神学的，好简洁，写起来好棒的感觉。
1、HDU 2222 Keywords Search 最基本的入门题了
就是求目标串中出现了几个模式串。
很基础了。使用一个int型的end数组记录，查询一次。
//======================
// HDU 2222
// 求目标串中出现了几个模式串
//====================
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std; struct Trie
{
int next[][],fail[],end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]-'a'] == -)
next[now][buf[i]-'a'] = newnode();
now = next[now][buf[i]-'a'];
}
end[now]++;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while( !Q.empty() )
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int query(char buf[])
{
int len = strlen(buf);
int now = root;
int res = ;
for(int i = ;i < len;i++)
{
now = next[now][buf[i]-'a'];
int temp = now;
while( temp != root )
{
res += end[temp];
end[temp] = ;
temp = fail[temp];
}
}
return res;
}
void debug()
{
for(int i = ;i < L;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = ;j < ;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
}
};
char buf[];
Trie ac;
int main()
{
int T;
int n;
scanf("%d",&T);
while( T-- )
{
scanf("%d",&n);
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%s",buf);
printf("%d\n",ac.query(buf));
}
return ;
}
这题和上题差不多，要输出出现模式串的id,用end记录id就可以了。还有trie树的分支是128的
题解here
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; struct Trie
{
int next[*][],fail[*],end[*];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = -;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char s[],int id)
{
int len = strlen(s);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][s[i]] == -)
next[now][s[i]] = newnode();
now=next[now][s[i]];
}
end[now]=id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
bool used[];
bool query(char buf[],int n,int id)
{
int len = strlen(buf);
int now = root;
memset(used,false,sizeof(used));
bool flag = false;
for(int i = ;i < len;i++)
{
now = next[now][buf[i]];
int temp = now;
while(temp != root)
{
if(end[temp] != -)
{
used[end[temp]] = true;
flag = true;
}
temp = fail[temp];
}
}
if(!flag)return false;
printf("web %d:",id);
for(int i = ;i <= n;i++)
if(used[i])
printf(" %d",i);
printf("\n");
return true;
}
};
char buf[];
Trie ac;
int main()
{
int n,m;
while(scanf("%d",&n) != EOF)
{
ac.init();
for(int i = ;i <= n;i++)
{
scanf("%s",buf);
ac.insert(buf,i);
}
ac.build();
int ans = ;
scanf("%d",&m);
for(int i = ;i <= m;i++)
{
scanf("%s",buf);
if(ac.query(buf,n,i))
ans++;
}
printf("total: %d\n",ans);
}
return ;
}
这题的变化也不大，就是需要输出每个模式串出现的次数，查询的时候使用一个数组进行记录就可以了
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std; char str[][];
struct Trie
{
int next[*][],fail[*],end[*];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = -;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char s[],int id)
{
int len = strlen(s);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][s[i]] == -)
next[now][s[i]] = newnode();
now = next[now][s[i]];
}
end[now] = id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i]=next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int num[];
void query(char buf[],int n)
{
for(int i = ;i < n;i++)
num[i] = ;
int len=strlen(buf);
int now=root;
for(int i=;i<len;i++)
{
now=next[now][buf[i]];
int temp = now;
while( temp != root )
{
if(end[temp] != -)
num[end[temp]]++;
temp = fail[temp];
}
}
for(int i = ;i < n;i++)
if(num[i] > )
printf("%s: %d\n",str[i],num[i]);
} }; char buf[];
Trie ac;
void debug()
{
for (int i = ; i < ac.L; i++)
{
printf("id = %3d ,fail = %3d ,end = %3d, chi = [",i,ac.fail[i],ac.end[i]);
for (int j = ; j < ; j++)
printf("%2d ",ac.next[i][j]);
printf("]\n");
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n) == )
{
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",str[i]);
ac.insert(str[i],i);
}
ac.build();
scanf("%s",buf);
ac.query(buf,n);
}
return ;
}
主要是解码过程，解码以后就是模板题了。
求出现的模式串的种类数
分支需要256个
//============================================================================
// Name : ZOJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std; struct Trie
{
int next[*][],fail[*],end[*];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = -;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(unsigned char buf[],int len,int id)
{
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]] == -)
next[now][buf[i]] = newnode();
now = next[now][buf[i]];
}
end[now] = id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]]=root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
bool used[];
int query(unsigned char buf[],int len,int n)
{
memset(used,false,sizeof(used));
int now = root;
for(int i = ;i < len;i++)
{
now = next[now][buf[i]];
int temp = now;
while( temp!=root )
{
if(end[temp] != -)
used[end[temp]]=true;
temp = fail[temp];
}
}
int res = ;
for(int i = ;i < n;i++)
if(used[i])
res++;
return res;
}
}; unsigned char buf[];
int tot;
char str[];
unsigned char s[];
unsigned char Get(char ch)
{
if( ch>='A'&&ch<='Z' )return ch-'A';
if( ch>='a'&&ch<='z' )return ch-'a'+;
if( ch>=''&&ch<='' )return ch-''+;
if( ch=='+' )return ;
else return ;
}
void change(unsigned char str[],int len)
{
int t=;
for(int i=;i<len;i+=)
{
buf[t++]=((str[i]<<)|(str[i+]>>));
if(i+ < len)
buf[t++]=( (str[i+]<<)|(str[i+]>>) );
if(i+ < len)
buf[t++]= ( (str[i+]<<)|str[i+] );
}
tot=t;
}
Trie ac;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;
while(scanf("%d",&n) == )
{
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",str);
int len = strlen(str);
while(str[len-]=='=')len--;
for(int j = ;j < len;j++)
{
s[j] = Get(str[j]);
}
change(s,len);
ac.insert(buf,tot,i);
}
ac.build();
scanf("%d",&m);
while(m--)
{
scanf("%s",str);
int len=strlen(str);
while(str[len-]=='=')len--;
for(int j = ;j < len;j++)
s[j] = Get(str[j]);
change(s,len);
printf("%d\n",ac.query(buf,tot,n));
}
printf("\n");
}
return ;
}
AC自动机+矩阵加速
这个时候AC自动机 的一种状态转移图的思路就很透彻了。
AC自动机就是可以确定状态的转移。
//============================================================================
// Name : POJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std; const int MOD=;
struct Matrix
{
int mat[][],n;
Matrix(){}
Matrix(int _n)
{
n = _n;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
mat[i][j]=;
}
Matrix operator *(const Matrix &b)const
{
Matrix ret=Matrix(n);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
for(int k=;k<n;k++)
{
int tmp=(long long)mat[i][k]*b.mat[k][j]%MOD;
ret.mat[i][j]=(ret.mat[i][j]+tmp)%MOD;
}
return ret;
}
};
struct Trie
{
int next[][],fail[];
bool end[];
int root,L;
int newnode()
{
for(int i=;i<;i++)
next[L][i]=-;
end[L++]=false;
return L-;
}
void init()
{
L=;
root=newnode();
}
int getch(char ch)
{
switch(ch)
{
case 'A':
return ;
break;
case 'C':
return ;
break;
case 'G':
return ;
break;
case 'T':
return ;
break;
}
}
void insert(char s[])
{
int len=strlen(s);
int now=root;
for(int i = ;i < len;i++)
{
if(next[now][getch(s[i])] == -)
next[now][getch(s[i])] = newnode();
now = next[now][getch(s[i])];
}
end[now]=true;
}
void build()
{
queue<int>Q;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]]==true)
end[now]=true;
for(int i = ;i < ;i++)
{
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
Matrix getMatrix()
{
Matrix res = Matrix(L);
for(int i=;i<L;i++)
for(int j=;j<;j++)
if(end[next[i][j]]==false)
res.mat[i][next[i][j]]++;
return res;
}
}; Trie ac;
char buf[]; Matrix pow_M(Matrix a,int n)
{
Matrix ret = Matrix(a.n);
for(int i = ; i < ret.n; i++)
ret.mat[i][i]=;
Matrix tmp=a;
while(n)
{
if(n&)ret=ret*tmp;
tmp=tmp*tmp;
n>>=;
}
return ret;
} int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF)
{
ac.init();
for(int i=;i<n;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
Matrix a=ac.getMatrix();
a=pow_M(a,m);
int ans=;
for(int i=;i<a.n;i++)
{
ans=(ans+a.mat[][i])%MOD;
}
printf("%d\n",ans);
}
return ;
}
这题和上题有些类似。但是需要求和。
所以给
矩阵增加一维，这样可以完美解决
题解here
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Matrix
{
unsigned long long mat[][];
int n;
Matrix(){}
Matrix(int _n)
{
n=_n;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
mat[i][j] = ;
}
Matrix operator *(const Matrix &b)const
{
Matrix ret = Matrix(n);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
for(int k=;k<n;k++)
ret.mat[i][j]+=mat[i][k]*b.mat[k][j];
return ret;
}
};
unsigned long long pow_m(unsigned long long a,int n)
{
unsigned long long ret=;
unsigned long long tmp = a;
while(n)
{
if(n&)ret*=tmp;
tmp*=tmp;
n>>=;
}
return ret;
}
Matrix pow_M(Matrix a,int n)
{
Matrix ret = Matrix(a.n);
for(int i=;i<a.n;i++)
ret.mat[i][i] = ;
Matrix tmp = a;
while(n)
{
if(n&)ret=ret*tmp;
tmp=tmp*tmp;
n>>=;
}
return ret;
}
struct Trie
{
int next[][],fail[];
bool end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = false;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]-'a'] == -)
next[now][buf[i]-'a'] = newnode();
now = next[now][buf[i]-'a'];
}
end[now] = true;
}
void build()
{
queue<int>Q;
fail[root]=root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]])end[now]=true;
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
Matrix getMatrix()
{
Matrix ret = Matrix(L+);
for(int i = ;i < L;i++)
for(int j = ;j < ;j++)
if(end[next[i][j]]==false)
ret.mat[i][next[i][j]] ++;
for(int i = ;i < L+;i++)
ret.mat[i][L] = ;
return ret;
}
void debug()
{
for(int i = ;i < L;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = ;j < ;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
}
};
char buf[];
Trie ac;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,L;
while(scanf("%d%d",&n,&L)==)
{
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
Matrix a = ac.getMatrix();
a = pow_M(a,L);
unsigned long long res = ;
for(int i = ;i < a.n;i++)
res += a.mat[][i];
res--; /*
* f[n]=1 + 26^1 + 26^2 +...26^n
* f[n]=26*f[n-1]+1
* {f[n] 1} = {f[n-1] 1}[26 0;1 1]
* 数是f[L]-1;
* 此题的L<2^31.矩阵的幂不能是L+1次，否则就超时了
*/
a = Matrix();
a.mat[][]=;
a.mat[][] = a.mat[][] = ;
a=pow_M(a,L);
unsigned long long ans=a.mat[][]+a.mat[][];
ans--;
ans-=res;
cout<<ans<<endl;
}
return ;
}
AC自动机+DP+高精度
好题
题解here
//============================================================================
// Name : POJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <map>
using namespace std;
map<char,int>mp;
int N,M,P;
struct Matrix
{
int mat[][];
int n;
Matrix(){}
Matrix(int _n)
{
n=_n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++)
mat[i][j] = ;
}
};
struct Trie
{
int next[][],fail[];
bool end[];
int L,root;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = false;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][mp[buf[i]]] == -)
next[now][mp[buf[i]]] = newnode();
now = next[now][mp[buf[i]]];
}
end[now] = true;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]]==true)end[now]=true;
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
Matrix getMatrix()
{
Matrix res = Matrix(L);
for(int i = ;i < L;i++)
for(int j = ;j < N;j++)
if(end[next[i][j]]==false)
res.mat[i][next[i][j]]++;
return res;
}
void debug()
{
for(int i = ;i < L;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = ;j < ;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
} }; /*
* 高精度，支持乘法和加法
*/
struct BigInt
{
const static int mod = ;
const static int DLEN = ;
int a[],len;
BigInt()
{
memset(a,,sizeof(a));
len = ;
}
BigInt(int v)
{
memset(a,,sizeof(a));
len = ;
do
{
a[len++] = v%mod;
v /= mod;
}while(v);
}
BigInt(const char s[])
{
memset(a,,sizeof(a));
int L = strlen(s);
len = L/DLEN;
if(L%DLEN)len++;
int index = ;
for(int i = L-;i >= ;i -= DLEN)
{
int t = ;
int k = i - DLEN + ;
if(k < )k = ;
for(int j = k;j <= i;j++)
t = t* + s[j] - '';
a[index++] = t;
}
}
BigInt operator +(const BigInt &b)const
{
BigInt res;
res.len = max(len,b.len);
for(int i = ;i <= res.len;i++)
res.a[i] = ;
for(int i = ;i < res.len;i++)
{
res.a[i] += ((i < len)?a[i]:)+((i < b.len)?b.a[i]:);
res.a[i+] += res.a[i]/mod;
res.a[i] %= mod;
}
if(res.a[res.len] > )res.len++;
return res;
}
BigInt operator *(const BigInt &b)const
{
BigInt res;
for(int i = ; i < len;i++)
{
int up = ;
for(int j = ;j < b.len;j++)
{
int temp = a[i]*b.a[j] + res.a[i+j] + up;
res.a[i+j] = temp%mod;
up = temp/mod;
}
if(up != )
res.a[i + b.len] = up;
}
res.len = len + b.len;
while(res.a[res.len - ] == &&res.len > )res.len--;
return res;
}
void output()
{
printf("%d",a[len-]);
for(int i = len-;i >= ;i--)
printf("%04d",a[i]);
printf("\n");
}
};
char buf[];
BigInt dp[][];
Trie ac;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout); while(scanf("%d%d%d",&N,&M,&P)==)
{
gets(buf);
gets(buf);
mp.clear();
int len = strlen(buf);
for(int i = ;i < len;i++)
mp[buf[i]]=i;
ac.init();
for(int i = ;i < P;i++)
{
gets(buf);
ac.insert(buf);
}
ac.build();
// ac.debug();
Matrix a= ac.getMatrix(); // for(int i = 0;i <a.n;i++)
// {
// for(int j=0;j<a.n;j++)printf("%d ",a.mat[i][j]);
// cout<<endl;
// } int now = ;
dp[now][] = ;
for(int i = ;i < a.n;i++)
dp[now][i] = ;
for(int i = ;i < M;i++)
{
now^=;
for(int j = ;j < a.n;j++)
dp[now][j] = ;
for(int j = ;j < a.n;j++)
for(int k = ;k < a.n;k++)
if(a.mat[j][k] > )
dp[now][k] = dp[now][k]+dp[now^][j]*a.mat[j][k];
// for(int j = 0;j < a.n;j++)
// dp[now][j].output();
}
BigInt ans = ;
for(int i = ;i < a.n;i++)
ans = ans + dp[now][i];
ans.output();
}
return ;
}
AC自动机+状态压缩DP
相当于在AC自动机上产生状态转移，然后进行dp
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int MOD=;
int n,m,k;
int dp[][][<<];
int num[]; struct Trie
{
int next[][],fail[],end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[],int id)
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]-'a']==-)
next[now][buf[i]-'a'] = newnode();
now = next[now][buf[i]-'a'];
}
end[now] |= (<<id);
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
end[now] |= end[fail[now]];
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int solve()
{
//memset(dp,0,sizeof(dp));
for(int i = ;i <= n;i++)
for(int j = ;j < L;j++)
for(int p = ;p < (<<m);p++)
dp[i][j][p]=;
dp[][][] = ;
for(int i = ;i < n;i++)
for(int j = ;j < L;j++)
for(int p = ;p< (<<m);p++)
if(dp[i][j][p] > )
{
for(int x = ;x < ;x++)
{
int newi = i+;
int newj = next[j][x];
int newp = (p|end[newj]);
dp[newi][newj][newp] += dp[i][j][p];
dp[newi][newj][newp]%=MOD;
}
}
int ans = ;
for(int p = ;p < (<<m);p++)
{
if(num[p] < k)continue;
for(int i = ;i < L;i++)
{
ans = (ans + dp[n][i][p])%MOD;
}
}
return ans;
}
};
char buf[];
Trie ac;
int main()
{
for(int i=;i<(<<);i++)
{
num[i] = ;
for(int j = ;j < ;j++)
if(i & (<<j))
num[i]++;
}
while(scanf("%d%d%d",&n,&m,&k)==)
{
if(n== && m== &&k==)break;
ac.init();
for(int i = ;i < m;i++)
{
scanf("%s",buf);
ac.insert(buf,i);
}
ac.build();
printf("%d\n",ac.solve());
}
return ;
}
需要输出字典序最小的解
在DP的时候加一个字符数组来记录就行了
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std; int a[];
int dp[][];
char str[][][]; bool cmp(char s1[],char s2[])
{
int len1=strlen(s1);
int len2=strlen(s2);
if(len1 != len2)return len1 < len2;
else return strcmp(s1,s2) < ;
} const int INF=0x3f3f3f3f;
struct Trie
{
int next[][],fail[],end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = -;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[],int id)
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]-'a'] == -)
next[now][buf[i]-'a'] = newnode();
now = next[now][buf[i]-'a'];
}
end[now] = id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
void solve(int n)
{
for(int i = ;i <= n;i++)
for(int j = ;j < L;j++)
dp[i][j] = -INF;
dp[][] = ;
strcpy(str[][],"");
char ans[];
strcpy(ans,"");
int Max = ;
char tmp[];
for(int i = ; i < n;i++)
for(int j = ;j < L;j++)
if(dp[i][j]>=)
{
strcpy(tmp,str[i][j]);
int len = strlen(tmp);
for(int k = ;k < ;k++)
{
int nxt=next[j][k];
tmp[len] = 'a'+k;
tmp[len+] = ;
int tt = dp[i][j];
if(end[nxt] != -)
tt+=a[end[nxt]]; if(dp[i+][nxt]<tt || (dp[i+][nxt]==tt && cmp(tmp,str[i+][nxt])))
{
dp[i+][nxt] = tt;
strcpy(str[i+][nxt],tmp);
if(tt > Max ||(tt==Max && cmp(tmp,ans)))
{
Max = tt;
strcpy(ans,tmp);
}
}
}
}
printf("%s\n",ans);
}
};
char buf[];
Trie ac;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;
int n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ac.init();
for(int i = ;i < m;i++)
{
scanf("%s",buf);
ac.insert(buf,i);
}
for(int i = ;i < m;i++)
scanf("%d",&a[i]);
ac.build();
ac.solve(n);
}
return ;
}
很简单的AC自动机+DP了
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Trie
{
int next[][],fail[];
bool end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = false;
return L-;
}
void init()
{
L = ;
root = newnode();
}
int getch(char ch)
{
if(ch == 'A')return ;
else if(ch == 'C')return ;
else if(ch == 'G')return ;
else if(ch == 'T')return ;
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][getch(buf[i])] == -)
next[now][getch(buf[i])] = newnode();
now = next[now][getch(buf[i])];
}
end[now] = true;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]])end[now] = true;//这里不要忘记
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int dp[][];
int solve(char buf[])
{
int len = strlen(buf);
for(int i = ;i <= len;i++)
for(int j = ;j < L;j++)
dp[i][j] = INF;
dp[][root] = ;
for(int i = ;i < len;i++)
for(int j = ;j < L;j++)
if(dp[i][j] < INF)
{
for(int k = ;k < ;k++)
{
int news = next[j][k];
if(end[news])continue;
int tmp;
if( k == getch(buf[i]))tmp = dp[i][j];
else tmp = dp[i][j] + ;
dp[i+][news] = min(dp[i+][news],tmp);
}
}
int ans = INF;
for(int j = ;j < L;j++)
ans = min(ans,dp[len][j]);
if(ans == INF)ans = -;
return ans;
} };
char buf[];
Trie ac;
int main()
{
int n;
int iCase = ;
while ( scanf("%d",&n) == && n)
{
iCase++;
ac.init();
while(n--)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%s",buf);
printf("Case %d: %d\n",iCase,ac.solve(buf));
}
return ;
}
11、ZOJ 3228 Searching the String
这题需要查询两种，一种是可重叠，一种是不可重叠的。
找模式串在目标串中的出现次数。
加一个数组记录上一次出现的位置，然后就可以求出不可重叠的了
//============================================================================
// Name : ZOJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std; struct Trie
{
int next[][],fail[],deep[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
L++;
return L-;
}
void init()
{
L = ;
root = newnode();
deep[root] = ;
}
int insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][buf[i]-'a'] == -)
{
next[now][buf[i]-'a'] = newnode();
deep[ next[now][buf[i]-'a'] ] = i+;
}
now = next[now][buf[i]-'a'];
}
return now;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int cnt[][];
int last[];
void query(char buf[])
{
int len = strlen(buf);
int now = root;
memset(cnt,,sizeof(cnt));
memset(last,-,sizeof(last));
for(int i = ;i < len;i++)
{
now = next[now][buf[i]-'a'];
int temp = now;
while(temp != root)
{
cnt[temp][]++;
if(i - last[temp] >= deep[temp])
{
last[temp] = i;
cnt[temp][]++;
}
temp = fail[temp];
}
}
}
};
Trie ac;
char str[];
char buf[];
int typ[],pos[];
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
int iCase = ;
while(scanf("%s",str)==)
{
iCase++;
printf("Case %d\n",iCase);
scanf("%d",&n);
ac.init();
for(int i = ;i < n;i++)
{
scanf("%d%s",&typ[i],buf);
pos[i]=ac.insert(buf);
}
ac.build();
ac.query(str);
for(int i = ;i < n;i++)
printf("%d\n",ac.cnt[pos[i]][typ[i]]);
printf("\n");
}
return ;
}
这题主要是状态的表示，就是记录ACGT出现的次数。
然后这个ACGT次数表示的时候，状态要转化。
题解here
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Trie
{
int next[][],fail[];
int end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
root = newnode();
}
int getch(char ch)
{
if(ch == 'A')return ;
else if(ch == 'C')return ;
else if(ch == 'G')return ;
else return ;
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len;i++)
{
if(next[now][getch(buf[i])] == -)
next[now][getch(buf[i])] = newnode();
now = next[now][getch(buf[i])];
}
end[now] ++;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
end[now] += end[fail[now]];/********/
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int dp[][***+];
int bit[];
int num[];
int solve(char buf[])
{
int len = strlen(buf);
memset(num,,sizeof(num));
for(int i = ;i < len;i++)
num[getch(buf[i])]++;
bit[] = (num[]+)*(num[]+)*(num[]+);
bit[] = (num[]+)*(num[]+);
bit[] = (num[]+);
bit[] = ;
memset(dp,-,sizeof(dp));
dp[root][] = ;
for(int A = ;A <= num[];A++)
for(int B = ;B <= num[];B++)
for(int C = ;C <= num[];C++)
for(int D = ;D <= num[];D++)
{
int s = A*bit[] + B*bit[] + C*bit[] + D*bit[];
for(int i = ;i < L;i++)
if(dp[i][s] >= )
{
for(int k = ;k < ;k++)
{
if(k == && A == num[])continue;
if(k == && B == num[])continue;
if(k == && C == num[])continue;
if(k == && D == num[])continue;
dp[next[i][k]][s+bit[k]] = max(dp[next[i][k]][s+bit[k]],dp[i][s]+end[next[i][k]]);
}
}
}
int ans = ;
int status = num[]*bit[] + num[]*bit[] + num[]*bit[] + num[]*bit[];
for(int i = ;i < L;i++)
ans = max(ans,dp[i][status]);
return ans;
}
};
char buf[];
Trie ac;
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
int iCase = ;
while( scanf("%d",&n) == && n)
{
iCase++;
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%s",buf);
printf("Case %d: %d\n",iCase,ac.solve(buf));
}
return ;
}
使用最短路预处理出状态的转移。这样可以优化很多
//============================================================================
// Name : HDU.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std; const int INF = 0x3f3f3f3f; struct Trie
{
int next[][],fail[],end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[],int id)
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len ;i++)
{
if(next[now][buf[i]-''] == -)
next[now][buf[i]-''] = newnode();
now = next[now][buf[i]-''];
}
end[now] = id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while( !Q.empty() )
{
int now = Q.front();
Q.pop();
if(end[fail[now]] == -)end[now] = -;
else end[now] |= end[fail[now]];
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int g[][];
int dp[][];
int cnt;
int pos[];
int dis[]; void bfs(int k)
{
queue<int>q;
memset(dis,-,sizeof(dis));
dis[pos[k]] = ;
q.push(pos[k]);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i = ; i< ;i++)
{
int tmp = next[now][i];
if(dis[tmp]< && end[tmp] >= )
{
dis[tmp] = dis[now] + ;
q.push(tmp);
}
}
}
for(int i = ;i < cnt;i++)
g[k][i] = dis[pos[i]];
} int solve(int n)
{ pos[] = ;
cnt = ;
for(int i = ;i < L;i++)
if(end[i] > )
pos[cnt++] = i;
for(int i = ; i < cnt;i++)
bfs(i); for(int i = ;i < (<<n);i++)
for(int j = ;j < cnt;j++)
dp[i][j] = INF;
dp[][] = ;
for(int i = ;i <(<<n);i++)
for(int j = ;j < cnt;j++)
if(dp[i][j]<INF)
{
for(int k = ;k < cnt;k++)
{
if(g[j][k] < )continue;
if( j == k)continue;
dp[i|end[pos[k]]][k] = min(dp[i|end[pos[k]]][k],dp[i][j]+g[j][k]);
}
}
int ans = INF;
for(int j = ;j < cnt;j++)
ans = min(ans,dp[(<<n)-][j]);
return ans;
}
};
Trie ac;
char buf[]; int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m) == )
{
if(n == && m == )break;
ac.init();
for(int i = ;i < n;i++)
{
scanf("%s",buf);
ac.insert(buf,<<i);
}
for(int i = ;i < m;i++)
{
scanf("%s",buf);
ac.insert(buf,-);
}
ac.build();
printf("%d\n",ac.solve(n));
}
return ;
}
这道题很神，数位DP和AC自动机结合，太强大了。
题解here
//============================================================================
// Name : ZOJ.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================ #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std; struct Trie
{
int next[][],fail[];
bool end[];
int root,L;
int newnode()
{
for(int i = ;i < ;i++)
next[L][i] = -;
end[L++] = false;
return L-;
}
void init()
{
L = ;
root = newnode();
}
void insert(char buf[])
{
int len = strlen(buf);
int now = root;
for(int i = ;i < len ;i++)
{
if(next[now][buf[i]-''] == -)
next[now][buf[i]-''] = newnode();
now = next[now][buf[i]-''];
}
end[now] = true;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = ;i < ;i++)
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]])end[now] = true;
for(int i = ;i < ;i++)
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
};
Trie ac; int bcd[][];
int change(int pre,int num)
{
if(ac.end[pre])return -;
int cur = pre;
for(int i = ;i >= ;i--)
{
if(ac.end[ac.next[cur][(num>>i)&]])return -;
cur = ac.next[cur][(num>>i)&];
}
return cur;
}
void pre_init()
{
for(int i = ;i <ac.L;i++)
for(int j = ;j <;j++)
bcd[i][j] = change(i,j);
}
const int MOD = ;
long long dp[][];
int bit[]; long long dfs(int pos,int s,bool flag,bool z)
{
if(pos == -)return ;
if(!flag && dp[pos][s]!=-)return dp[pos][s];
long long ans = ;
if(z)
{
ans += dfs(pos-,s,flag && bit[pos]==,true);
ans %= MOD;
}
else
{
if(bcd[s][]!=-)ans += dfs(pos-,bcd[s][],flag && bit[pos]==,false);
ans %= MOD;
}
int end = flag?bit[pos]:;
for(int i = ;i<=end;i++)
{
if(bcd[s][i]!=-)
{
ans += dfs(pos-,bcd[s][i],flag&&i==end,false);
ans %=MOD;
}
}
if(!flag && !z)dp[pos][s] = ans;
return ans;
} long long calc(char s[])
{
int len = strlen(s);
for(int i = ;i < len;i++)
bit[i] = s[len--i]-'';
return dfs(len-,,,);
}
char str[];
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
int n;
while(T--)
{
ac.init();
scanf("%d",&n);
for(int i = ;i < n;i++)
{
scanf("%s",str);
ac.insert(str);
}
ac.build();
pre_init();
memset(dp,-,sizeof(dp));
int ans = ;
scanf("%s",str);
int len = strlen(str);
for(int i = len -;i >=;i--)
{
if(str[i]>'')
{
str[i]--;
break;
}
else str[i] = '';
}
ans -= calc(str);
ans %=MOD;
scanf("%s",str);
ans += calc(str);
ans %=MOD;
if(ans < )ans += MOD;
printf("%d\n",ans);
}
return ;
}
最新文章
- C# 集合类 ：（Array、 Arraylist、List、Hashtable、Dictionary、Stack、Queue）
- 关于JS
- .使用 HTML+CSS 实现如图布局，border-widht 5px，一个格子大小是 50*50，hover时候边框变为红色（兼容IE6+，考虑语义化的结构）
- 第 一 百 天上课 PHP TP框架 数据库修改和删除
- JsRender实用教程(tag else使用、循环嵌套访问父级数据)
- 如何正大光明的使用 google 进行搜索
- listToString
- SQL Server主键自动生成_表and存储过程
- vue-cli——vue-resource登录注册实例
- c++函数常用
- 用samba来创建windows下的文件共享
- Flask里面session的基本操作
- 前端 -----jQuery的事件绑定和解绑
- Learning to Rank Short Text Pairs with Convolutional Deep Neural Networks（paper）
- TZOJ 1705 Dining(拆点最大流)
- MongoDB（课时26 聚合(取的集合个数)）
- 匹配追踪算法（MP）简介
- OAuth2认证有一定的了解
- 51nod 1548 欧姆诺姆和糖果 （制约关系优化枚举）
- ASP.NET缺少程序集引用怎么办