AC自动机（简单版）
题目链接
Luogu 3808
题解
AC自动机裸题，如果不加$last$优化会TLE。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+1;
int ch[N][26],f[N],cnt;
int l[N];
int tag[N];
void add(char *s){
int n=strlen(s);
int x=0;
for(int i=0;i<n;++i){
int c=s[i]-'a';
if(ch[x][c]==-1){
ch[x][c]=++cnt;
for(int j=0;j<26;++j)ch[cnt][j]=-1;
}
x=ch[x][c];
}
tag[x]++;
}
void getfail(){
queue<int>q;
for(int i=0;i<26;++i)
if(~ch[0][i])l[ch[0][i]]=f[ch[0][i]]=0,q.push(ch[0][i]);
else ch[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<26;++i){
if(tag[ch[f[x]][i]])l[ch[x][i]]=ch[f[x]][i];
else l[ch[x][i]]=l[ch[f[x]][i]];
if(~ch[x][i])f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
else ch[x][i]=ch[f[x]][i];
}
}
}
bool vis[N];
int get(char *s){
int n=strlen(s);
int x=0,ret=0;
for(int i=0;i<n;++i){
x=ch[x][s[i]-'a'];
for(int j=x;j;j=l[j])
if(!vis[j])vis[j]=1,ret+=tag[j];
}
return ret;
}
int n;
char s[N];
int main(){
cin>>n;
for(int i=0;i<26;++i)ch[0][i]=-1;
for(int i=0;i<n;++i)scanf("%s",s),add(s);
getfail();
scanf("%s",s);
cout<<get(s)<<endl;
}
|
AC自动机（加强版）
题目链接
Luogu 3796
题解
AC自动机裸题。不加$last$优化也能过，多组数据注意清零。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+1;
int tr[N][26],f[N],cnt,ans[N];
int l[N];
int tag[N];
void add(char *s,int fa){
int n=strlen(s);
int x=0;
for(int i=0;i<n;++i){
int c=s[i]-'a';
if(tr[x][c]==-1){
tr[x][c]=++cnt;
for(int j=0;j<26;++j)tr[cnt][j]=-1;
}
x=tr[x][c];
}
tag[x]=fa;
}
void getfail(){
queue<int>q;
for(int i=0;i<26;++i)
if(~tr[0][i])l[tr[0][i]]=f[tr[0][i]]=0,q.push(tr[0][i]);
else tr[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<26;++i){
if(tr[x][i]==-1){tr[x][i]=tr[f[x]][i];continue;}
int y=tr[x][i];
q.push(y);
f[y]=tr[f[x]][i];
}
}
}
bool vis[N];
void get(char *s){
int n=strlen(s);
int x=0,ret=0;
for(int i=0;i<n;++i){
x=tr[x][s[i]-'a'];
for(int j=x;j;j=f[j])
if(tag[j])ans[tag[j]]++;
}
}
int n;
char s[256][256];
char s1[N];
void put(char *s){
int n=strlen(s);
for(int i=0;i<n;++i)putchar(s[i]);
printf("\n");
}
int main(){
while(scanf("%d",&n)!=EOF){
if(!n)return 0;
cnt=0;
for(int i=0;i<26;++i)tr[0][i]=-1;
for(int i=1;i<=n;++i)scanf("%s",s[i]),add(s[i],i);
getfail();
scanf("%s",s1);get(s1);
int res=*max_element(ans+1,ans+n+1);
printf("%d\n",res);
for(int i=1;i<=n;++i)if(ans[i]==res)put(s[i]);
for(int i=1;i<=n;++i)ans[i]=0;
for(int i=1;i<=cnt;++i)tag[i]=f[i]=l[i]=0;
}
}
|
HNOI2006 最短母串
题目链接
Luogu 2322
题解
考虑$n$很小的性质，第一眼以为是状态压缩DP暴力转移（实际也能做，但是很难写），正解应该是将在AC自动机上DP。根据AC自动机的性质，易知一条路径即代表一个字符串。设$f[i][S]$表示当前走到第$i$号节点，已经覆盖串的集合为$S$的最小步数状态数为$50n2^n$，直接用BFS更新即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e2+5;
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
char s[13][51];
int n;
struct kd{
int x,y;
}X,Y;
struct AC{
int cnt,tr[N][26],f[N],tag[N],pos[N];
int d[N][1<<12];
int prex[N][1<<12],prey[N][1<<12];
void init(){
cnt=0;
memset(tr[0],-1,sizeof(tr[0]));
}
void add(char *s,int k){
int n=strlen(s);
int x=0;
for(int i=0;i<n;++i){
int c=s[i]-'A';
if(tr[x][c]==-1){
tr[x][c]=++cnt;
pos[cnt]=c;
memset(tr[cnt],-1,sizeof(tr[cnt]));
tag[cnt]=0;
}
x=tr[x][c];
}
tag[x]|=1<<k;
}
void getf(){
queue<int>q;
f[0]=0;
for(int i=0;i<26;++i)
if(~tr[0][i])f[tr[0][i]]=0,q.push(tr[0][i]);
else tr[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
tag[x]|=tag[f[x]];
for(int i=0;i<26;++i){
if(~tr[x][i])f[tr[x][i]]=tr[f[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[f[x]][i];
}
}
}
void output(int x,int y){
static int q[N];
while(x){
q[++q[0]]=pos[x]+'A';
int x1=x,y1=y;
x=prex[x1][y1];
y=prey[x1][y1];
}
reverse(q+1,q+q[0]+1);
for(int i=1;i<=q[0];++i)printf("%c",(char)q[i]);
}
void solve(){
getf();
int S=(1<<n)-1;
memset(d,-1,sizeof(d));
queue<kd>q;
X.x=0;X.y=0;
q.push(X);d[0][0]=0;
prex[0][0]=0;prey[0][0]=0;
while(!q.empty()){
X=q.front();q.pop();
for(int i=0;i<26;++i)
if(tr[X.x][i]){
int to=tr[X.x][i];
Y.x=to;Y.y=X.y|tag[to];
if(d[Y.x][Y.y]==-1){
prex[Y.x][Y.y]=X.x;prey[Y.x][Y.y]=X.y;
d[Y.x][Y.y]=d[X.x][X.y]+1;
if(Y.y==S){
output(Y.x,Y.y);
printf("\n");
exit(0);
}
q.push(Y);
}
}
}
}
}T;
int main(){
scanf("%d",&n);
T.init();
for(int i=0;i<n;++i){
scanf("%s",s[i]);
T.add(s[i],i);
}
T.solve();
}
|
BJOI2017 魔法咒语
题目链接
Luogu 3715
题解
设$f[i][L]$为走到第$i$号节点，此时字符串长度（即路径长度）为$L$的方案数，那么由于字符集在此题中被限制为了一个个的字符串，所以需要预处理$go[i][j]$表示从$i$号节点出发后经过第$j$个基本词汇后所到达的节点，如果其中经过禁忌词语，则初始化为$-1$表示不可到达。那么DP方程如下：（$len[j]$表示基本词汇$j$的长度）
$$f[go[i][j]][L+len[j]] += f[i][L] (go[i][j]!=-1)$$
观察数据范围，朴素的DP只能通过$60 \ percents$的数据，剩余$L<=10^8$且$len[j]<=2$的部分分，可以通过矩阵乘法优化，用$f[i][j]$表示从$i$号节点一步到达$j$号节点的方案数，可以处理$len[j]=1$的情况。对于$len[j]=2$的情况，对于每个节点$i$设一个虚拟节点$b[i]$，然后$f[i][b[j]]$表示从$i$一步到$b[j]$的方案数，再从$b[j]$向$j$连一条边即可（即f$[b[j]][j]=1$）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3+1;
const ll mod = 1e9+7;
int n,m,L,cnt,len[51];
char a[51][401],b[51][401];
void mul(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
int t1k;
struct Matrix{
ll a[401][401];
friend Matrix operator * (Matrix a,Matrix b){
Matrix c;
memset(c.a,0,sizeof(c.a));
for(int i=0;i<=t1k;++i)
for(int j=0;j<=t1k;++j){
for(int k=0;k<=t1k;++k)
(c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mod;
}
return c;
}
}res,c;
struct AC{
int tr[N][26],f[N],tag[N],val[N],to[N][51];
void init(){
cnt=0;
memset(tr[0],-1,sizeof(tr[0]));
}
void add(char *s,int h){
int x=0;
int n=strlen(s);
for(int i=0;i<n;++i){
int c=s[i]-'a';
if(tr[x][c]==-1){
tr[x][c]=++cnt;
val[cnt]=i;
memset(tr[cnt],-1,sizeof(tr[cnt]));
}
x=tr[x][c];
}
tag[x]=h;
}
void getf(){
queue<int>q;
for(int i=0;i<26;++i)
if(~tr[0][i])f[tr[0][i]]=0,q.push(tr[0][i]);
else tr[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
tag[x]|=tag[f[x]];
for(int i=0;i<26;++i)
if(~tr[x][i])f[tr[x][i]]=tr[f[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[f[x]][i];
}
}
int go(int i,char *s){
int n=strlen(s);
int x=i;
if(tag[x])return -1;
for(int j=0;j<n;++j){
x=tr[x][s[j]-'a'];
if(tag[x])return -1;
}
return x;
}
void A(){
static int dp[N][101];
dp[0][0]=1;
for(int l=0;l<=L;++l)
for(int i=0;i<=cnt;++i)
for(int j=0;j<n;++j)
if(len[j]+l<=L){
int y=to[i][j];
if(y==-1)continue;
mul(dp[y][len[j]+l],dp[i][l]);
}
int ans=0;
for(int i=0;i<=cnt;++i)mul(ans,dp[i][L]);
printf("%d\n",ans);
}
void B(){
t1k=2*cnt+1;
int tp=cnt+1;
for(int i=0;i<=cnt;++i)res.a[i+tp][i]=1;
for(int i=0;i<=2*cnt+1;++i)c.a[i][i]=1;
for(int i=0;i<=cnt;++i)
for(int j=0;j<n;++j){
int y=to[i][j];
if(y==-1)continue;
if(len[j]==1)res.a[i][y]++;
else res.a[i][y+tp]++;
}
while(L){
if(L&1)c=c*res;
L>>=1;
res=res*res;
}
ll ans=0;
for(int i=0;i<=cnt;++i)(ans+=c.a[0][i])%=mod;
printf("%lld\n",ans);
}
void solve(){
init();
for(int i=0;i<m;++i)add(b[i],1);
getf();
for(int i=0;i<=cnt;++i)
for(int j=0;j<n;++j)
to[i][j]=go(i,a[j]);
if(L<=100)A();
else B();
}
}T;
int main(){
scanf("%d%d%d",&n,&m,&L);
for(int i=0;i<n;++i)scanf("%s",a[i]),len[i]=strlen(a[i]);
for(int i=0;i<m;++i)scanf("%s",b[i]);
T.solve();
}
|
BJWC2011 禁忌
题目链接
Luogu 4569
题解
首先考虑对于一个给定的串，如何求其禁忌伤害，这是一个经典的贪心问题，即线段覆盖问题，正确的姿势是按右端点排序，能取的尽量取即可，如果去除存在覆盖的禁忌串（一定没有只取被覆盖的子串优越），那么姿势等价于按左端点排序，且尽可能的取。
考虑在AC自动机上的贪心，即为从根节点出发每次走到一个禁忌串后，直接返回根节点（因为禁忌串之间不能相互覆盖），重复过程直到路径长度为$L$并将答案加上返回次数除以$2^{len}$，考虑如何用DP优化此过程，仍然设$f[i][L]$表示走到$i$号节点，路径长度为$L$的概率，那么显然有（$0$表示根节点,$tag$表示是否为禁忌串。）
$$f[0][L+1]+=f[i][L]+1/alphabet \ (tag[tr[x][i]]=1)$$
$$f[tr[x][i]][L+1]+=f[i][L]+1/alphabet \ (tag[tr[x][i]]=0)$$
考虑如何将统计答案。在贪心的过程中，每次访问到禁忌串时不仅要返回根节点，还要将答案加上到当前节点的概率，即新建一个节点$g$表示答案节点，那么同样有
$$f[g][L+1]+=f[i][L]+1/alphabet \ (tag[tr[x][i]]=1)$$
即可以用矩阵乘法优化此过程，并且需要设定$matrix[g][g]=1$，矩阵$L$次方代表$1−L$前缀和的贡献，即为答案。
#include<bits/stdc++.h>
#define mp make_pair
#define fr first
#define sd second
#define pii pair<int,int>
using namespace std;
typedef long long ll;
typedef long double db;
const int N = 1e2+1;
int cnt,n,L,ml,len[6],tr[N][26],f[N],tag[N];
char s[6][N];
struct matrix{
db a[N][N];
friend matrix operator * (matrix a,matrix b){
matrix c;
for(int i=0;i<=cnt+1;++i)
for(int j=0;j<=cnt+1;++j)
c.a[i][j]=0;
for(int i=0;i<=cnt+1;++i)
for(int j=0;j<=cnt+1;++j)
for(int k=0;k<=cnt+1;++k)
c.a[i][j]+=a.a[i][k]*b.a[k][j];
return c;
}
}res;
matrix qpow(ll b){
matrix c;
for(int i=0;i<=cnt+1;++i)
for(int j=0;j<=cnt+1;++j)
c.a[i][j]=(i==j);
while(b){
if(b&1)c=c*res;
b>>=1;
res=res*res;
}
return c;
}
void solve(){
db k=1.00/(db)ml;
for(int i=0;i<=cnt;++i)
for(int j=0;j<ml;++j){
int y=tr[i][j];
if(tag[y])res.a[i][0]+=k,res.a[i][cnt+1]+=k;
else res.a[i][y]+=k;
}
res.a[cnt+1][cnt+1]=1;
printf("%.8lf",(double)qpow(L).a[0][cnt+1]);
}
int add(char *s){
int n=strlen(s),x=0;
for(int i=0;i<n;++i){
int c=s[i]-'a';
if(tr[x][c]==-1){
tr[x][c]=++cnt;
memset(tr[cnt],-1,sizeof(tr[cnt]));
}
x=tr[x][c];
}
tag[x]=1;
return n;
}
void getf(){
queue<int>q;
for(int i=0;i<ml;++i)
if(~tr[0][i])f[tr[0][i]]=0,q.push(tr[0][i]);
else tr[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
tag[x]|=tag[f[x]];
for(int i=0;i<ml;++i){
if(~tr[x][i])f[tr[x][i]]=tr[f[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[f[x]][i];
}
}
}
int main(){
memset(tr[0],-1,sizeof(tr[0]));
scanf("%d%d%d",&n,&L,&ml);
for(int i=1;i<=n;++i)scanf("%s",s[i]),len[i]=add(s[i]);
getf();
solve();
}
|
SCOI2012 喵星球上的点名
题目链接
Luogu 2336
题解
由于本题中字符集过大，肯定不能将数组开满，需要用$map$来存储儿子，且不能在每次新建节点时将儿子都表示成$−1$，那么就要默认为$0$。同理需要将根节点设为$1$，并赋值$tr[0][i]=1$，在$getfail$的时候，也应该直接暴力跳$fail$。由于数据较水，这样即可通过此题。（正解为后缀数组+主席树）
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e5+5;
map<int,int>tr[N];
map<int,int>::iterator it;
int n,m,L,cnt,f[N],g[N],ans[N],res[N],id[N];
int vis[N],vis1[N],T;
vector<int>a[N],b[N],tag[N];
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
void add(int *s,int n,int fa){
int x=1;
for(int i=1;i<=n;++i){
int c=s[i];
if(!tr[x][c])tr[x][c]=++cnt;
x=tr[x][c];
}
tag[x].pb(fa);
}
void getf(){
queue<int>q;
q.push(1);
while(!q.empty()){
int x=q.front();q.pop();
for(it=tr[x].begin();it!=tr[x].end();++it){
int t=it->first,k=f[x];
while(!tr[k][t])k=f[k];
f[it->second]=tr[k][t];
q.push(it->second);
}
}
}
int cala(int g){
int x=1,ret=0;
for(int i=0;i<a[g].size();++i){
int to=a[g][i];
while(!tr[x][to])x=f[x];x=tr[x][to];
for(int j=x;j;j=f[j]){
if(vis1[j]==T)break;vis1[j]=T;
for(int k=0;k<tag[j].size();++k){
int y=tag[j][k];
if(vis[y]!=T)vis[y]=T,++ret,ans[y]++;
}
}
}
return ret;
}
int calb(int g){
int x=1,ret=0;
for(int i=0;i<b[g].size();++i){
int to=b[g][i];
while(!tr[x][to])x=f[x];x=tr[x][to];
for(int j=x;j;j=f[j]){
if(vis1[j]==T)break;vis1[j]=T;
for(int k=0;k<tag[j].size();++k){
int y=tag[j][k];
if(vis[y]!=T)vis[y]=T,++ret,ans[y]++;
}
}
}
return ret;
}
int main(){
L=10001;cnt=1;f[1]=0;
for(int i=0;i<L;++i)tr[0][i]=1;
n=read();m=read();
for(int i=1,k;i<=n;++i){
k=read();for(int j=1;j<=k;++j)a[i].pb(read());
k=read();for(int j=1;j<=k;++j)b[i].pb(read());
}
for(int i=1,k;i<=m;++i){
k=read();for(int j=1;j<=k;++j)g[j]=read();
add(g,k,i);
}
getf();
for(int i=1;i<=n;++i){
++T;
res[i]=
cala(i)+
calb(i);
}
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
for(int i=1;i<=n;++i){
printf("%d",res[i]);
if(i!=n)printf(" ");
}
return 0;
}
|
HAOI2017 字符串
题目链接
Luogu 3735
题解
对于每个询问串和初始串，将问题转化为其前后缀的匹配（初始串的表示为$x,y$询问串的表示为为$a,b$）。先将所有询问串建到AC自动机上，然后建出$fail$树。
同$NOI2011$阿狸的打字机一样，对于一个初始串的子串能匹配到询问串当且仅当在$fail$树中，$x[j]$在$a[j]$的子树中，且$y[j+k+1]$在$b[j+k+1]$的子树中，该算法可以通过子树差分来实现。但是如果直接统计所有前后缀的话，明显会存在重复的情况：
初始串：$aaab$
询问串：$abab$
$k=2$
此时显然询问串与初始串匹配了两回（即$x[0]−>y[3]$与$a[0]−>b[3]$和$x[1]−>y[4]$与$a[1]−>b[4]$）。
一般性的，以上算法实际上求的是$k1 \in [1,k]$中所有可以匹配的$k1$的个数，那么$k$匹配个数即为$[1,k]$匹配个数与$[1,k−1]$匹配个数的差。（需要注意在求解$[1,k−1]$的时候，$a,b,x,y$的边界条件需要与求解$[1,k]$时对齐）
#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define fr first
#define pb push_back
#define sd second
using namespace std;
typedef long long ll;
const int N = 4e5+5;
int k;
char s[N],p[N];
int n,ans[N];
vector<pii>sum1[N],sum2[N];
vector<int>g[N],ch1[N],ch2[N];
int st[N],ed[N],totw;
struct lb{
int a[N];
lb(){
memset(a,0,sizeof(a));
}
void add(int x){
for(;x<=totw;x+=x&-x)a[x]++;
}
int sum(int x){
int ret=0;
for(;x;x-=x&-x)ret+=a[x];
return ret;
}
int get(int x){
return sum(ed[x])-sum(st[x]-1);
}
}T[2];
void _debug(int *a){
for(int i=0;a[i];++i)printf("%d ",a[i]);
cout<<endl;
}
struct __AC{
int tr[N][95],f[N],cnt,x[N],y[N];
void add(char *s,int n,int *q,bool flag){
int x=0;
q[0]=q[n+1]=0;
for(int i=flag?n:1;flag?i>=1:i<=n;flag?--i:++i){
int c=s[i]-33;
if(tr[x][c]==-1){
tr[x][c]=++cnt;
memset(tr[cnt],-1,sizeof(tr[cnt]));
}
q[i]=x=tr[x][c];
}
}
void getf(){
queue<int>q;
for(int i=0;i<95;++i)
if(~tr[0][i])q.push(tr[0][i]);
else tr[0][i]=0;
while(!q.empty()){
int x=q.front();q.pop();
g[f[x]].pb(x);
for(int i=0;i<95;++i)
if(~tr[x][i])f[tr[x][i]]=tr[f[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[f[x]][i];
}
}
void dfs(int x){
st[x]=++totw;
for(int i=0;i<g[x].size();++i)dfs(g[x][i]);
ed[x]=totw;
}
void getans(int x){
for(int i=0;i<sum1[x].size();++i){pii t=sum1[x][i];ans[t.sd]-=T[0].get(t.fr);}
for(int i=0;i<sum2[x].size();++i){pii t=sum2[x][i];ans[t.sd]+=T[1].get(t.fr);}
for(int i=0;i<ch1[x].size();++i){int t=ch1[x][i];T[0].add(st[t]);}
for(int i=0;i<ch2[x].size();++i){int t=ch2[x][i];T[1].add(st[t]);}
for(int i=0;i<g[x].size();++i)getans(g[x][i]);
for(int i=0;i<sum1[x].size();++i){pii t=sum1[x][i];ans[t.sd]+=T[0].get(t.fr);}
for(int i=0;i<sum2[x].size();++i){pii t=sum2[x][i];ans[t.sd]-=T[1].get(t.fr);}
}
void solve(){
memset(tr[0],-1,sizeof(tr[0]));
int len=strlen(s+1);
for(int i=1;i<=n;++i){
scanf("%s",p+1);
int m=strlen(p+1);
if(m<=k)ans[i]=len-m+1;
else{
add(p,m,x,0);add(p,m,y,1);
for(int j=k+1;j<=m+1;++j)sum1[x[j-k-1]].pb(mp(y[j],i));
for(int j=k+1;j<=m;++j)sum2[x[j-k]].pb(mp(y[j],i));
}
}
getf();
int pt;
x[0]=x[len+1]=y[0]=y[len+1]=0;
pt=0;for(int i=1;i<=len;++i)x[i]=pt=tr[pt][s[i]-33];
pt=0;for(int i=len;i>=1;--i)y[i]=pt=tr[pt][s[i]-33];
for(int j=k+1;j<=len+1;++j)ch1[x[j-k-1]].pb(y[j]);
for(int j=k+1;j<=len;++j)ch2[x[j-k]].pb(y[j]);
dfs(0);
getans(0);
}
}AC;
int main(){
scanf("%d%s%d",&k,s+1,&n);
AC.solve();
for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
}
|
TJOI2013 单词
COCI2015 Divljak
