2020-2021:teams:legal_string:jxm2001:字符串_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_2 [2020/08/30 10:59] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_2 [2020/10/01 20:08] (当前版本) jxm2001 [算法例题] |
||
|---|---|---|---|
| 行 520: | 行 520: | ||
| === 例题六 === | === 例题六 === | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/7817/G|2020牛客国庆集训派对day1 G题]] | ||
| + | |||
| + | == 题意 == | ||
| + | |||
| + | 给定 $m$ 个禁止串 $S_i$，求长度为 $n$ 且子串不含任意禁止串的字符串数。 | ||
| + | |||
| + | 数据保证 $\sum_{i=1}^m |S_i|\le 100,n\le 10^9$。 | ||
| + | |||
| + | == 题解 == | ||
| + | |||
| + | 考虑建立 $\text{fail}$ 树，然后标记所有禁止串终止结点以及其在 $\text{fail}$ 树中的子树。 | ||
| + | |||
| + | 然后将树边转化为 $\sum_{i=1}^m |S_i|\times \sum_{i=1}^m |S_i|$ 的邻接矩阵 $A$ 来进行状态转移，套用矩阵快速幂即可快速求解，最后答案即为 $\sum A_{0,i}$。 | ||
| + | |||
| + | 时间复杂度 $O\left((\sum_{i=1}^m |S_i|)^3\log n\right)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXS=105,Mod=1e9+7; | ||
| + | struct Matrix{ | ||
| + | int ele[MAXS][MAXS]; | ||
| + | Matrix operator * (const Matrix &b){ | ||
| + | Matrix c; | ||
| + | mem(c.ele,0); | ||
| + | _for(i,0,MAXS) | ||
| + | _for(j,0,MAXS) | ||
| + | _for(k,0,MAXS) | ||
| + | c.ele[i][j]=(c.ele[i][j]+1LL*ele[i][k]*b.ele[k][j])%Mod; | ||
| + | return c; | ||
| + | } | ||
| + | }; | ||
| + | Matrix quick_pow(Matrix a,int n){ | ||
| + | Matrix ans; | ||
| + | mem(ans.ele,0); | ||
| + | _for(i,0,MAXS) | ||
| + | ans.ele[i][i]=1; | ||
| + | while(n){ | ||
| + | if(n&1) | ||
| + | ans=ans*a; | ||
| + | a=a*a; | ||
| + | n>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | namespace AC{ | ||
| + | int ch[MAXS][26],val[MAXS],fail[MAXS],sz; | ||
| + | void insert(char *s){ | ||
| + | int len=strlen(s),pos=0; | ||
| + | _for(i,0,len){ | ||
| + | int c=s[i]-'a'; | ||
| + | if(!ch[pos][c]) | ||
| + | ch[pos][c]=++sz; | ||
| + | pos=ch[pos][c]; | ||
| + | } | ||
| + | val[pos]=1; | ||
| + | } | ||
| + | int getAns(int n){ | ||
| + | queue<int>q; | ||
| + | _for(i,0,26){ | ||
| + | if(ch[0][i]) | ||
| + | q.push(ch[0][i]); | ||
| + | } | ||
| + | while(!q.empty()){ | ||
| + | int u=q.front();q.pop(); | ||
| + | _for(i,0,26){ | ||
| + | if(ch[u][i]){ | ||
| + | fail[ch[u][i]]=ch[fail[u]][i]; | ||
| + | val[ch[u][i]]|=val[ch[fail[u]][i]]; | ||
| + | q.push(ch[u][i]); | ||
| + | } | ||
| + | else | ||
| + | ch[u][i]=ch[fail[u]][i]; | ||
| + | } | ||
| + | } | ||
| + | Matrix a; | ||
| + | _rep(i,0,sz){ | ||
| + | _rep(j,0,sz) | ||
| + | a.ele[i][j]=0; | ||
| + | _for(j,0,26){ | ||
| + | if(!val[ch[i][j]]) | ||
| + | a.ele[i][ch[i][j]]++; | ||
| + | } | ||
| + | } | ||
| + | a=quick_pow(a,n); | ||
| + | int ans=0; | ||
| + | _rep(i,0,sz) | ||
| + | ans=(ans+a.ele[0][i])%Mod; | ||
| + | return ans; | ||
| + | } | ||
| + | } | ||
| + | char s[MAXS]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | while(m--){ | ||
| + | int len=read_int(); | ||
| + | scanf("%s",s); | ||
| + | AC::insert(s); | ||
| + | } | ||
| + | enter(AC::getAns(n)); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | === 例题七 === | ||
| [[https://www.luogu.com.cn/problem/UVA11019|UVA11019]] | [[https://www.luogu.com.cn/problem/UVA11019|UVA11019]] | ||
| 行 539: | 行 646: | ||
| 于是对 $a$ 的每列跑 $\text{KMP}$ 算法记录 $b$ 的出现数即可。时间复杂度 $O(nm+xy)$。 | 于是对 $a$ 的每列跑 $\text{KMP}$ 算法记录 $b$ 的出现数即可。时间复杂度 $O(nm+xy)$。 | ||
| - | 注意上述方法可以拓展到任意维字符串匹配。 | + | 注意上述方法中 $AC$ 自动机起到了降维的作用，且可以拓展到任意维字符串匹配。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/字符串_2.1598756383.txt.gz · 最后更改: 2020/08/30 10:59 由 jxm2001
