「刷题笔记」AC自动机
自动AC机
Keywords Research
板子题，同luoguP3808，不过是多测。
然后多测不清空，\(MLE\)两行泪。
板子放一下
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define S 1000010
ll n;
char tmp[S];
ll vcn=0;
struct vertex
{
ll fail;
ll son[30];
ll num;
}tree[S];
ll q[S],l,r;
void build()
{
ll len=strlen(tmp);
ll rt=0;
for(int i=0;i<len;i++)
{
ll t=tmp[i]-'a';
if(!tree[rt].son[t])tree[rt].son[t]=++vcn;
rt=tree[rt].son[t];
}
tree[rt].num++;
}
void getfail()
{
l=r=0;
tree[0].fail=0;
for(int i=0;i<26;i++)
{
if(tree[0].son[i])
{
tree[tree[0].son[i]].fail=0;
q[++r]=tree[0].son[i];
}
}
while(l<r)
{
ll u=q[++l],v;
for(int i=0;i<26;i++)
{
v=tree[u].son[i];
if(v)
{
tree[v].fail=tree[tree[u].fail].son[i];
q[++r]=v;
}
else tree[u].son[i]=tree[tree[u].fail].son[i];
}
}
}
ll AC()
{
ll len=strlen(tmp);
ll u=0,ans=0,v;
for(int i=0;i<len;i++)
{
ll t=tmp[i]-'a';
u=tree[u].son[t];
v=u;
while(v&&tree[v].num!=-1)
{
ans+=tree[v].num;
tree[v].num=-1;
v=tree[v].fail;
}
}
return ans;
}
void clear()
{
memset(tree,0,sizeof tree);
vcn=0;
}
ll T;
ZZ_zuozhe
{
scanf("%d",&T);
while(T--)
{
clear();
scanf("%d",&n);
while(n--)
{
scanf("%s",tmp);
build();
}
getfail();
scanf("%s",tmp);
printf("%d\n",AC());
}
return 0;
}
玄武密码
求最大匹配前缀。多模式串。
似乎是板子……（然而当时并没打熟
跳fail的时候需要把能匹配的位置都标上，能匹配上的肯定是前缀。
然后再扫一下\(trie\)，找之前的标记，并取最大下标。
求最大匹配后缀的话是不是要倒一下……一会问问
其实只有四个字母应该压下空间的，不过这题不压也能过（懒 ZZ 懒）
然后就是以后要看清题里给的是小写字母还是大写的，要不数组会越界于无形之中（如果数据正好又比较小，\(wa\)都不知道怎么\(wa\)的……
TJOI2013 单词
文章单词之间是有空格的，分开插入就行，刚开始想多了……
（哪有英语文章不写空格的啊喂
\(fail\)有一个性质就是，一个串的\(fail\)其实是这个串的一个后缀，也就是这个串包含了他的\(fail\)
所以说，一个单词是多少单词的\(fail\)，他就出现了多少次
考虑一个\(fail\)指针组成的\(fail\)树，那么一个单词出现次数就是\(fail\)树中以他为根的子树大小
刚开始以为是要在\(trie\)上做一个\(dfs\)，但是这样统计实际上是不完全的，例如：
abc
babc
这时只考虑了一个串是另外一个串的前缀的情况。
核心代码长这样：
for(int i=vcn;i>=1;i--)tree[tree[q[i]].fail].num+=tree[q[i]].num;
for(int i=0;i<n;i++)printf("%lld\n",tree[tail[i]].num);
POI2000 病毒
看题意很迷惑，然后画了点图，发现大概是要在\(trie\)上找到一个不经过串尾的环
不经过串尾保证他不会和某个模式串匹配，环保证他能无限循环
然后\(dfs\)就行了
注意：一个结点不断跳\(fail\)，肯定是能跳到\(0\)的，但是需要保证这一路上没有危险节点，所以标记危险节点的时候，除了标模式串尾的结点，不如把在多次跳\(fail\)后会到达危险节点的结点也标上。
然后dfs时跳的是两个儿子，而没有判\(0\)，这是因为之前在\(getfail\)的时候已经把这样不存在的儿子引到父亲的\(fail\)的儿子了，所以其实没有影响的。
代码或许需要存一下……
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define S 60005
ll n;
struct vertex
{
ll fail;
ll son[2];
}tree[S];
ll dg[S];
ll q[S];
ll vcn=0;
char tmp[S];
void ins()
{
ll rt=0;
ll len=strlen(tmp);
for(int i=0;i<len;i++)
{
if(!tree[rt].son[tmp[i]-'0'])tree[rt].son[tmp[i]-'0']=++vcn;
rt=tree[rt].son[tmp[i]-'0'];
}
dg[rt]=1;
}
void getfail()
{
ll l,r;
l=r=0;
tree[0].fail=0;
for(int i=0;i<2;i++)
{
if(tree[0].son[i])
{
tree[tree[0].son[i]].fail=0;
q[++r]=tree[0].son[i];
}
}
while(l<r)
{
ll u=q[++l],v;
for(int i=0;i<2;i++)
{
v=tree[u].son[i];
if(v)
{
tree[v].fail=tree[tree[u].fail].son[i];
dg[v]|=dg[tree[v].fail];
q[++r]=v;
}
else tree[u].son[i]=tree[tree[u].fail].son[i];
}
}
}
bool vis[S]={0},fvis[S]={0};
bool dfs(ll rt)
{
if(vis[rt])return 1;
if(dg[rt]||fvis[rt])return 0;
vis[rt]=fvis[rt]=1;
bool res=0;
if(!dg[tree[rt].son[0]])res|=dfs(tree[rt].son[0]);
if(!dg[tree[rt].son[1]])res|=dfs(tree[rt].son[1]);
//if(!dg[tree[rt].fail])res|=dfs(tree[rt].fail);
vis[rt]=0;
return res;
}
ZZ_zuozhe
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
ins();
}
getfail();
if(dfs(0))puts("TAK");
else puts("NIE");
return 0;
}
最短母串
警醒：把一个数类型设成\(char\)，白调\(2h\)
一点点dp（其实主要是状压），但我可以送命了qaq
trie树先建出来
\(n\)的范围不是很大，所以可以考虑用状压记录各个字符串是否被用过，至于状态，因为一个字符串用过肯定经过了他的结尾那个结点，所以每个结点记录上状态，在建树的时候结尾要附上这个字符串的状态\((1<<x)\)
根据fail的性质，getfail时，结点和他的fail的状态要合并，因为到了这个节点就是可以选择跳fail的，就相当于已经走了之后的路了
为什么此处必定跳fail呢？因为这里如果有fail就说明这个节点的后面可以匹配了，这个时候不跳串会更长，浪费，不合题意。
用一个vis数组记录是否被访问过，\(vis[i][j]\)代表节点\(i\)是否以状态\(j\)被访问过，用来避免bfs时由于重复的字符串得不到最优解的情况
那么做一个bfs，每次队头取出一个结点和他在进队时处于的状态，枚举他的所有儿子，然后合并状态，再塞进队列里，等着下一次用
如果出现了状态填满了，就输出，这里利用一个小技巧，把之前处理的时候把状态编号指向他父亲的编号，输出方便
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ZZ_zuozhe int main()
#define NS 5005
ll n;
char tmp[55];
struct vertex
{
ll fail;
ll son[26];
ll st;
}tree[NS];
ll vcn=0;
queue<ll> q;
void getfail()
{
for(int i=0;i<26;i++)
{
if(tree[0].son[i])
{
q.push(tree[0].son[i]);
}
}
while(!q.empty())
{
ll u=q.front();
q.pop();
//cout<<u<<endl;
for(int i=0;i<26;i++)
{
if(tree[u].son[i])
{
tree[tree[u].son[i]].fail=tree[tree[u].fail].son[i];
tree[tree[u].son[i]].st|=tree[tree[tree[u].fail].son[i]].st;
q.push(tree[u].son[i]);
}
else tree[u].son[i]=tree[tree[u].fail].son[i];
}
}
}
bool vis[NS][1<<12|1];
char ans[NS];
ll nod=0;
ll fa[NS*(1<<12|1)],an[NS*(1<<12|1)];
ll tot=0;
queue<ll>q1,q2;
ZZ_zuozhe
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
ll len=strlen(tmp);
ll rt=0;
for(int j=0;j<len;j++)
{
ll t=tmp[j]-'A';
if(!tree[rt].son[t])tree[rt].son[t]=++vcn;
rt=tree[rt].son[t];
}
tree[rt].st|=(1<<(i-1));
}
getfail();
vis[0][0]=1;
q1.push(0);
q2.push(0);
ll tt=0;
while(!q1.empty())
{
ll rt=q1.front(),st=q2.front();
q1.pop();q2.pop();
if(st==((1<<n)-1))
{
while(tt)
{
ans[++nod]=an[tt];
tt=fa[tt];
}
for(int i=nod;i>0;i--)putchar(ans[i]+'A');
return 0;
}
for(int i=0;i<26;i++)
{
if(!tree[rt].son[i])continue;
if(!vis[tree[rt].son[i]][st|tree[tree[rt].son[i]].st])
{
vis[tree[rt].son[i]][st|tree[tree[rt].son[i]].st]=1;
q1.push(tree[rt].son[i]);
q2.push(st|tree[tree[rt].son[i]].st);
fa[++tot]=tt;
an[tot]=i;
}
}
tt++;
}
return 0;
}
文本生成器
也是dp
既然让求可读文本总数，不妨反着想，用总方案数\(26^n\)减去不碰边界的方案数
其实跟前面那个病毒挺像的，都是标记危险节点，然后遍历的时候故意不走
设\(f[i][j]\)为在\(j\)点，有\(i\)位的时候，不碰边界的方案总数
那么
\]
最后快速幂求\(26^n\)，再减去所有\(f[m][~]\)的和，记得取模。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ZZ_zuozhe int main()
#define ull unsigned long long
#define P 10007
#define N 65
#define M 105
#define S 6005
ll n,m;
struct vertex
{
ll fail;
ll son[26];
bool dg;
}tree[S];
char tmp[M];
ll vcn=0;
void ins()
{
ll len=strlen(tmp);
ll rt=0;
for(int i=0;i<len;i++)
{
ll t=tmp[i]-'A';
if(!tree[rt].son[t])tree[rt].son[t]=++vcn;
rt=tree[rt].son[t];
}
tree[rt].dg=1;
}
void getfail()
{
queue<ll>Q;
for(int i=0;i<26;i++)if(tree[0].son[i])Q.push(tree[0].son[i]);
while(!Q.empty())
{
ll rt=Q.front();
Q.pop();
for(int i=0;i<26;i++)
{
ll v=tree[rt].son[i];
if(v)
{
tree[v].fail=tree[tree[rt].fail].son[i];
tree[v].dg|=tree[tree[v].fail].dg;
Q.push(v);
}
else tree[rt].son[i]=tree[tree[rt].fail].son[i];
}
}
}
ll f[M][S];
ll ksm(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%P;
a=a*a%P;
b>>=1;
}
return res%P;
}
ll sol()
{
f[0][0]=1;
ll res=0;
for(int i=1;i<=m;i++)
{
for(int j=0;j<=vcn;j++)
{
for(int k=0;k<26;k++)
{
if(!tree[tree[j].son[k]].dg)
{
f[i][tree[j].son[k]]+=f[i-1][j];
f[i][tree[j].son[k]]%=P;
}
}
}
}
res=ksm(26,m);
ll tmp=0;
for(int i=0;i<=vcn;i++)tmp=(tmp+f[m][i])%P;
return ((res-tmp)%P+P)%P;
}
ZZ_zuozhe
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
ins();
}
getfail();
printf("%lld",sol());
return 0;
}
背单词
警醒：线段树\(rt<<1\)打成\(rt\)，白调\(3h\)
为什么今天全是\(sb\)错误啊qaq
AC自动机，dfs序，线段树
首先分析下题意：每个单词是后一个单词的子串，这个放在AC自动机里怎么理解呢
其实，每一个单词是后一个单词的子串，就是说后一个单词某一个结点的fail指向了前一个单词的结尾节点，此时后一个单词的前缀的后缀就是前一个单词，显然满足条件。
于是，问题转化为：前后两个单词满足后一个单词某一个结点的fail是前一个单词的结尾节点，从fail树的角度考虑，即在fail树中，后一个单词某结点在fail树以前一个单词结尾节点为根的子树中
关于子树的判断，dfs序是绝佳的选择
首先明确如果某个节点的价值，是他的fail树子树里任何一个节点都有机会享受到的，而dfs序是连续的，那么这就可以用线段树维护
因为取的是子序列，所以每次取出一个单词，枚举其中的每一个字母，选取当前能得到价值最大的一个节点（线段树维护最大值，单点查询），这个价值加上当前单词的价值，就是前\(i\)个单词的最大价值。
得到最大价值后，这个最大价值是可以让前一个单词结尾节点的fail子树内所有结点共享的，既然记录了dfs序，这里就可以用线段树的区间修改来解决。
这个过程中，如果遇到价值为负的单词，可以直接跳过，因为前面单词的选择不会对后面单词是否选择产生什么影响，那就干脆不要选负的。
在前面处理完毕后，枚举得到的每一个最大值，就可以得出全局的最大值。
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ull undigned long long
#define ZZ_zuozhe int main()
#define S 1000005
#define pb push_back
#define INF 100000000
ll T,n;
ll w[S];
char tmp[S];
vector<char> v[S];
struct trie
{
ll fail;
ll son[30];
ll num;
}tree[S];
ll vcn=1;
void ins()
{
ll len=strlen(tmp);
ll rt=1;
for(int i=0;i<len;i++)
{
ll t=tmp[i]-'a';
if(!tree[rt].son[t])tree[rt].son[t]=++vcn;
rt=tree[rt].son[t];
}
///
}
void getfail()
{
queue<int> Q;
tree[1].fail=1;
for(int i=0;i<26;i++)
{
if(tree[1].son[i])tree[tree[1].son[i]].fail=1;
Q.push(tree[1].son[i]);
}
while(!Q.empty())
{
ll u=Q.front();
Q.pop();
for(int i=0;i<26;i++)
{
ll v=tree[u].son[i];
if(v)
{
tree[v].fail=tree[tree[u].fail].son[i];
Q.push(v);
}
else tree[u].son[i]=tree[tree[u].fail].son[i];
}
}
}
struct edge
{
ll u,v;
}e[S<<1];
ll head[S],next[S],cnt=0;
void add(ll u,ll v)
{
++cnt;
e[cnt].u=u;
e[cnt].v=v;
next[cnt]=head[u];
head[u]=cnt;
}
ll l[S],r[S],tt=0;
void dfs(ll rt)
{
l[rt]=++tt;
for(int i=head[rt];i;i=next[i])dfs(e[i].v);
r[rt]=tt;
}
struct xds
{
ll son[2];
ll lz;
ll val;
}t[S<<2];
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
inline void upd(ll rt){t[rt].val=max(t[rt<<1].val,t[rt<<1|1].val);}
void build(ll rt,ll l,ll r)
{
t[rt].val=-INF;
t[rt].lz=0;
if(l==r)
{
return;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
upd(rt);
}
void pushdown(ll rt)
{
if(t[rt].lz)
{
t[rt<<1].lz=max(t[rt<<1].lz,t[rt].lz);
t[rt<<1|1].lz=max(t[rt<<1|1].lz,t[rt].lz);
t[rt<<1].val=max(t[rt<<1].val,t[rt].lz);
t[rt<<1|1].val=max(t[rt<<1|1].val,t[rt].lz);
t[rt].lz=0;
}
}
ll query(ll rt,ll l,ll r,ll nl,ll nr)
{
if(nl<=l&&r<=nr)
{
return t[rt].val;
}
pushdown(rt);
ll m=(l+r)>>1;
ll res=0;
if(m>=nl)res=max(res,query(lson,nl,nr));
if(m<nr)res=max(res,query(rson,nl,nr));
return res;
}
void update(ll rt,ll l,ll r,ll nl,ll nr,ll val)
{
if(nl<=l&&r<=nr)
{
t[rt].val=max(t[rt].val,val);
t[rt].lz=max(t[rt].lz,val);
return;
}
pushdown(rt);
ll m=(l+r)>>1;
if(m>=nl)update(lson,nl,nr,val);
if(m<nr)update(rson,nl,nr,val);
upd(rt);
}
ll f[S];
void clear()
{
memset(tree,0,sizeof tree);
memset(e,0,sizeof e);
memset(head,0,sizeof head);
memset(next,0,sizeof next);
cnt=1;
memset(l,0,sizeof l);
memset(r,0,sizeof r);
tt=0;
memset(t,0,sizeof t);
for(int i=1;i<=n;i++)v[i].clear();
memset(f,0,sizeof f);
}
ZZ_zuozhe
{
//freopen("owo.in","r",stdin);
//freopen("owo.out","w",stdout);
scanf("%d",&T);
while(T--)
{
//ll a=0;
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s%d",tmp,&w[i]);
//if(w[i]>0)a+=w[i];
ins();
ll len=strlen(tmp);
for(int j=0;j<len;j++)v[i].pb(tmp[j]);
}
getfail();
for(int i=2;i<=vcn;i++)add(tree[i].fail,i);
dfs(1);
build(1,1,tt);
for(int i=1;i<=n;i++)
{
if(w[i]<=0)continue;
ll len=v[i].size();
ll rt=1,ma=0;
for(int j=0;j<len;j++)
{
ll t=v[i][j]-'a';
rt=tree[rt].son[t];
ma=max(ma,query(1,1,tt,l[rt],l[rt]));
}
f[i]=max(ma,0)+w[i];
update(1,1,tt,l[rt],r[rt],f[i]);
}
ll ans=-INF;
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
printf("%d\n",ans);
//cout<<a<<' '<<tt<<' '<<vcn<<endl;
}
return 0;
}
好长啊我想学压行
密码
awsl
第一眼感觉是限长度版的最短母串，然后写假了，只有\(20pts\)
其实是挺像的，都用了状压……但是这个不太一样
最短母串里因为要求最短，所以我们转移的时候判了一个是否有儿子，但这个不要求最短，有时甚至必须有多余的字符，所以按照最短母串的思路是走不通的
之前在一篇题解里好像看见过“AC自动机+DP，一般都是设\(f[i][j]\)，\(i\)是当前匹配长度，\(j\)是当前节点，然后视情况再加一维其他信息”
这里我们用状压思想，所以就加上一维已有单词的状态，即设\(f[i][j][S]\)，\(i,j\)意义同上，\(S\)为当前状态
则有转移方程：
\]
做这样的题时，注意在\(getfail\)时同时将\(fail\)结点的状态合并至本结点。
答案即为\(\sum f[L][][S_满]\)
关于输出：
我们先用dfs预处理出所有结点的位置是否能通向一个符合要求的串，然后输出时利用他剪枝，如果不通就不走了。输出就是一边dfs一边存下当前答案，够长度了就输出
（这题不写输出给\(50pts\)？？？）
打算有时间来一遍二刷，不留代码了
[BJWC2011]禁忌
ac自动机版GT考试
首先要读懂题……这种带有剧情的题有时候会读着很麻烦……
- 字母集\(A\)上的每个非空字符串对应了一个魔法。其中\(A\)是包含了前\(alphabet\)个小写字母的集合。
- 有一个集合\(T\)，包含了\(N\)个字母集\(A\)上的字符串。\(T\)中的每一串称为一个禁忌串（Taboo string）
- 一个魔法，或等价地，其对应的串\(s\)因为包含禁忌而对使用者造成的伤害按以下方式确定：把\(s\)分割成若干段，考虑其中是禁忌串的段的数目，不同的分割可能会有不同的数目，其最大值就是这个伤害。
第一条这个\(A\)里头有一堆小写字母，每个非空字符串就是把这些字母随便拼（这条似乎无关紧要
第二条就是给一个集合\(T\)，里面都是满足要求的\(A\)中的字符串，这些串叫禁忌串，一会会给
第三条就是在一个字符串中，有多少相互不重叠的禁忌串，就造成多大伤害
那么题中给出了所有禁忌串，现在需要我们求一个长度为\(len\)的，字母从\(A\)中取的，随机的串中禁忌串数量的期望（因为要达到题中的最大情况，就是在切的时候恰好把存在的每一个不重叠的禁忌串都切出来
考虑到多模式串，我们可以建出AC自动机
考虑匹配的过程，每个节点如果是一个禁忌串的末尾，就应当直接切，也就是前面扔掉，再从头进行匹配（假如此时有一个也正在匹配的更长的禁忌串，去匹配它显然不优）这个时候，对答案产生了贡献，我们把这部分贡献计入答案，并将它纳入之后的转移中。而如果这时并不能匹配成功，就枚举此节点所有的儿子并等概率转移。
转移类似于这个的意思：
\]
这个形式就可以用矩阵加速。那么考虑初始矩阵。
我们的矩阵下标为节点编号，\(M[i][j]\)代表的是匹配位置\(i\rightarrow j\)的期望
另外，我们设\(M^n\)中的\(M[i][vcn+1]\)为以\(i\)为开头，共有\(n\)位时对答案的总贡献，那么\(M[0][vcn+1]\)即为答案。
设置初始矩阵：
\(\begin{cases}
if(tree[tree[i].son[j]].dg)\\
M_0[i][0]+=\frac{1}{alphabet}（回到树根，供下一步转移）\\
M_0[i][vcn+1]+=\frac{1}{alphabet}（计入答案）\\
else\\
M_0[i][j]+=\frac{1}{alphabet}（向下走一步）\\
特别地，设M_0[vcn+1][vcn+1]=1，便于转移
\end{cases}\)
之后就是简单的矩阵快速幂啥的，代码很好写不放，期望题大概主要考察思路吧
最新文章
- Python中的条件判断和循环
- ExtJs4 笔记（14） layout 布局
- WCF服务部署到IIS7.5
- struts 标签库注解
- How to Notify Command to evaluate in mvvmlight
- ubuntu系统根目录下各个目录用途说明
- Linux学习笔记7——linux中的静态库和动态库
- jquery easy ui 学习 （4） window 打开之后 限制操纵后面元素属性
- git 克隆本地仓库
- hdu4513之manacher算法
- textarea内容太多， 鼠标点击全部显示
- 如何利用keytool查看一个apk的签名
- java通过shield链接Elasticsearch
- bmob云代码中生成缩略图
- LeetCode - Fruit Into Baskets
- python 字符串操作。。
- 第十三章 redis-cluster原理
- XE6 c++builder 设置 font size GetPropInfo SetOrdProp
- 遭遇java.lang.NoClassDefFoundError: org/apache/tomcat/PeriodicEventListener
- PHP——简单的表单提交