• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Gym100221C Forbidden Subwords

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

Link
先建出AC自动机,然后把终止状态去掉,这样Trie图上的一条路径就对应了一个不包含Forbidden Subwords的字符串。
考虑如何对单向无限的串计数。单向无限的串是一条从根开始的无限长的路径,最后肯定会走到某个scc(自环也是强连通的)。
如果一个scc包含了不止一个简单环,那么我们就可以在两个环上来回走,答案就是\(+\infty\)
那么现在所有的scc都是一个简单环。
如果某个从根出发的路径经过了两个scc,那么就可以在第一个scc上走任意多圈,答案也是\(+\infty\)
那么现在一条合法的路径就是从根出发经过一些没有自环的单点走到一个scc,然后沿着scc走无限圈。
此时路径条数就是有限的了,可以在缩点之后的Trie图上求出。
现在考虑双向无限,相比于单向无限,我们可以比较近似的认为它是从某个scc开始到某个scc结束(可能是同一个)。
因此第二个判断答案为\(+\infty\)的条件就变成了存在一条经过三个scc路径。
最长路径和计数都可以在缩点之后的Trie图上求出。
注意要保留Trie图中的重边来判断是否是简单环。

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int N=10007;
char str[13];int n,m,cnt,tot,t,top,f,ans,vis[N],fa[N],ch[N][6],bel[N],dfn[N],low[N],stk[N],is[N],tag[N],mx[N],sum[N];
std::vector<int>e[N],a[N];std::queue<int>q;
void ins(){int p=0;for(int l=strlen(str+1),i=1,c;i<=l;p=ch[p][c],++i)if(!ch[p][c=str[i]-'a'])ch[p][c]=++cnt;vis[p]=1;}
void build()
{
    for(int c=0;c<n;++c) if(ch[0][c]) q.push(ch[0][c]);
    for(int x,c;!q.empty();) for(x=q.front(),q.pop(),vis[x]|=vis[fa[x]],c=0;c<n;++c) ch[x][c]? q.push(ch[x][c]),fa[ch[x][c]]=ch[fa[x]][c]:ch[x][c]=ch[fa[x]][c];
    for(int x=0;x<=cnt;++x) for(int c=0;c<n;++c) if(!vis[ch[x][c]]) e[x].push_back(ch[x][c]);
}
void pop(int u)
{
    ++tot;int s=0;
    do ++s,bel[stk[top]]=tot,a[tot].push_back(stk[top]); while(stk[top--]^u);
    for(int u:a[tot]) for(int v:e[u]) s-=bel[v]==tot;
    s>=0? is[tot]=!s:f=1;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++t,stk[++top]=u;
    for(int v:e[u]) if(!dfn[v]) tarjan(v),low[u]=std::min(low[u],low[v]); else if(!bel[v]) low[u]=std::min(low[u],low[v]);
    if(dfn[u]==low[u]) pop(u);
}
void dp(int x)
{
    if(tag[x]) return; tag[x]=1;
    for(int u:a[x]) for(int v:e[u]) if(bel[v]^x) dp(bel[v]),sum[x]+=sum[bel[v]],mx[x]=std::max(mx[x],mx[bel[v]]);
    if(is[x]) ++mx[x],++sum[x],ans+=sum[x];
}
int main()
{
    freopen("forbidden.in","r",stdin); freopen("forbidden.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%s",str+1),ins();
    build(),tarjan(0),dp(bel[0]),printf("%d",f||mx[bel[0]]>=3? -1:ans);
}

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
【转载】C#之int与Java之Integer的区别发布时间:2022-07-13
下一篇:
C++和Java中枚举enum的用法发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap