又好久没做过 AC 自动机的题了,做道练练手罢(
首先考虑对于某个固定的字符串怎样求出它的伤害,我们考虑贪心,每碰到出现一个模式串就将其划分为一段,最终该字符串的代价就是划分的次数。具体来说我们记录一个 \(pre\) 表示上一次在 \(pre\) 与 \(pre-1\) 划分为一段,我们从前往后扫一遍,每扫到一个 \(i\),就检验 \(s[pre…i],s[pre+1…i],s[pre+2…i],\cdots,s[i…i]\) 中是否有子串在模式串中出现过,如果有就令答案加 \(1\),并将 \(pre\) 赋为 \(i\)。正确性显然。
显然这种多模式串的题可以想到 AC 自动机。建出自动机,然后设 \(dp_{i,j}\) 表示已经填好了前 \(i\) 个位置上的字符,当前匹配到了 \(j\) 号节点的概率,转移显然可以枚举 \(j\) 的子节点 \(k\),\(dp_{i+1,k}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\),那么怎么体现”划分完的部分就不考虑了“呢?很简单,如果 \(k\) 是匹配节点,那我们就令 \(dp_{i+1,\text{root}}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\) instead of \(dp_{i+1,k}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\),并且由于期望的线性性,这边答案产生了 \(1\) 的贡献,故还需令 \(ans\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\)。
由于这题 \(len\) 数据范围很大,故可以套路地想到矩阵快速幂。建立转移矩阵,快速幂转移即可。时间复杂度 \((\sum|s|)\log len\)。还有一个小问题,就是这个 \(ans\) 如何一边求 \(dp\) 的值一遍维护。我们考虑令矩阵的大小扩大 \(1\),即一般的矩阵快速幂我们是 \(\begin{bmatrix}dp_{i,1}\\dp_{i,2}\\\cdots\\dp_{i,m}\end{bmatrix}\) 转移到 \(\begin{bmatrix}dp_{i+1,1}\\dp_{i+1,2}\\\cdots\\dp_{i+1,m}\end{bmatrix}\),而这题我们考虑增加一行 \(ans\),即从 \(\begin{bmatrix}dp_{i,1}\\dp_{i,2}\\\cdots\\dp_{i,m}\\ans\end{bmatrix}\) 转移到 \(\begin{bmatrix}dp_{i+1,1}\\dp_{i+1,2}\\\cdots\\dp_{i+1,m}\\ans\end{bmatrix}\)。具体来说对于一个点 \(j\),如果它的儿子中有 \(c\) 个匹配点,那么我们就令 \(ans\leftarrow ans+dp_{i,j}\times\dfrac{c}{\text{alpha}}\),这个也可在转移矩阵中表示出来。
最后再多说一句,如果你矩阵乘法是使用矩阵乘向量,也就是矩阵在前,向量在后的写法,要将转移到的位置设作行号,从哪个位置转移设为列号,我因为这地方写反了调了好久……xtbz
typedef long double ld;
const int MAXL=75;
const int ALPHA=26;
int n,len,alpha;char buf[MAXL+5];
int ch[MAXL+5][ALPHA+2],fail[MAXL+5],ncnt=0;
bool ed[MAXL+5];
void insert(char *s){
int len=strlen(s+1),cur=0;
for(int i=1;i<=len;i++){
if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++ncnt;
cur=ch[cur][s[i]-'a'];
} ed[cur]=1;
}
void getfail(){
queue<int> q;
for(int i=0;i<alpha;i++) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<alpha;i++){
if(ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);
else ch[x][i]=ch[fail[x]][i];
}
}
}
struct mat{
ld a[MAXL+5][MAXL+5];
mat(){memset(a,0,sizeof(a));}
mat operator *(const mat &rhs){
mat res;
for(int i=0;i<=ncnt;i++) for(int j=0;j<=ncnt;j++)
for(int k=0;k<=ncnt;k++) res.a[i][j]+=a[i][k]*rhs.a[k][j];
return res;
}
};
int main(){
scanf("%d%d%d",&n,&len,&alpha);
for(int i=1;i<=n;i++) scanf("%s",buf+1),insert(buf);
getfail();mat trs,mul,tt;
for(int i=0;i<=ncnt;i++) for(int j=0;j<alpha;j++){
if(ed[ch[i][j]]) trs.a[0][i]+=1.0/alpha,trs.a[ncnt+1][i]+=1.0/alpha;
else trs.a[ch[i][j]][i]+=1.0/alpha;
} ncnt++;trs.a[ncnt][ncnt]=1;
for(int i=0;i<=ncnt;i++) mul.a[i][i]=1;
for(;len;len>>=1,trs=trs*trs) if(len&1) mul=mul*trs;
tt.a[0][0]=1;tt=mul*tt;printf("%.10Lf\n",tt.a[ncnt][0]);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章