bzoj 3473: 字符串（后缀自动机）_clover_hxy的博客-程序员宝宝

题目描述

传送门

题目大意：给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？

题解

同bzoj3277

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 200003
#define LL long long
using namespace std;
int tot,n,k,point[N],nxt[N],v1[N],ch[N][30],fa[N],c[N];
int v[N],pos[N],l[N],mark[N],cnt,root,last,np,q,p,nq,head[N],next[N];
char s[N];
LL ct[N],ans[N];
void add(int x,int y)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v1[tot]=y;
}
void extend(int x,int col)
{
    int c=s[x]-'a'+1; np=++cnt;
    p=last; last=np; l[np]=l[p]+1;
    for (;!ch[p][c]&&p;p=fa[p]) ch[p][c]=np;
    if (!p) fa[np]=root;
    else {
        q=ch[p][c];
        if (l[p]+1==l[q]) fa[np]=q;
        else {
            nq=++cnt; l[nq]=l[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[nq]));
            fa[nq]=fa[q]; mark[nq]=mark[q]; ct[nq]=ct[q];
            fa[q]=fa[np]=nq;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
    add(col,np);
    for (;np;np=fa[np])
     if (mark[np]!=col) {
        mark[np]=col; 
        ct[np]++;
     }
     else break;
}
void build(int x,int y)
{
    tot++; next[tot]=head[x]; head[x]=tot; v[tot]=y;
}
void dfs(int x)
{
    for (int i=head[x];i;i=next[i]){
        ans[v[i]]+=ans[x];
        dfs(v[i]);
    }
}
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d%d",&n,&k);
    root=++cnt;
    for (int i=1;i<=n;i++) {
        scanf("%s",s+1); int len=strlen(s+1);
        last=root;
        for (int j=1;j<=len;j++) extend(j,i);
    }
    for (int i=1;i<=cnt;i++) v[l[i]]++;
    for (int i=1;i<=cnt;i++) v[i]+=v[i-1];
    for (int i=1;i<=cnt;i++) pos[v[l[i]]--]=i;
    tot=0;
    for (int i=1;i<=cnt;i++) {
        int t=pos[i];
        build(fa[t],t);
        ans[t]=(ct[t]>=k?l[t]-l[fa[t]]:0);
    }
    c[1]=0;
    dfs(1);
    for (int i=1;i<=n;i++) {
        LL sum=0;
        for (int j=point[i];j;j=nxt[j])
         sum+=ans[v1[j]];
        printf("%lld ",sum);
    }
    printf("\n");
}

本文链接：https://blog.csdn.net/clover_hxy/article/details/67633838

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

从零开始学android编程！来一份全面的面试宝典练练手，系列教学_普通网友的博客-程序员宝宝

职业生涯规划Android系统的市场地位Android程序开发的技能成长经验Android程序员为什么需要学习Html5Android软件工程师为什么不会被前端替代为什么小程序无法替代原生开发为什么Html5无法取代NativeAPPHtml5在Android中的应用场景如何成为一名合格的高级Android程序员1、应用层开发，不限于各种产品，主要还是Android或iOS原生开发，主要是各种性能优化。2、嵌入式开发，不限于各种开发板子，物联网，智能家居3、安全开发，不限于各种反逆向

【数据库】【课程设计】商品销售信息管理系统设计_商品销售管理系统设计_哎呀，何必呢的博客-程序员宝宝

商品销售信息管理系统设计1.设计目的2.需求分析2.1系统业务分析2.2系统数据处理分析2.3系统数据字典3.系统设计3.1系统开发框架3.2系统功能组成设计3.2.1 系统功能组成3.2.2 子系统功能模块设计3.3数据库结构设计3.3.1 商品管理系统的对象/实体3.3.2 概念模型转换为关系模型3.3.2 定义关系模型4.数据库实施与数据准备4.1数据库实施4.2数据准备5.系统功能模块设计与开发5.1模块划分5.2系统功能模块设计与开发5.2.1 登录模块5.2.2 插入订单5.2.3 删除订单5.

yii2url地址后面加上.html,Yii2 URL路由规则设置过程详解_weixin_39639040的博客-程序员宝宝

在实际上线时候肯定要自定义规则好利于SEO或者浏览，以及精简URL的长度等等。我们就需要设置URL的规则了，YII2配置就不多说了。'urlManager'=>['enablePrettyUrl'=>true,//路由的路径化'showScriptName'=>false,'suffix'=>'.html',//后缀'rules'=>[//为...

mac10.9+php5.5.15+brew0.9.5的安装_dianbutang4605的博客-程序员宝宝

Brew 是 Mac 下面的包管理工具，通过 Github 托管适合 Mac 的编译配置以及 Patch，可以方便的安装开发工具。 Mac 自带ruby 所以安装起来很方便，同时它也会自动把git也给你装上。官方网站： http://brew.sh安装方法：?1ruby -e "$(curl -fsSL http...

linux中查看库依赖文件,linux下查看程序依赖的库_高分子科学前沿的博客-程序员宝宝

在x86下,为了查看程序所依赖的库,可以使用但如果是使用arm-linux-gcc 等交叉编译环境编译出来的程序,则要使用库用于将相似函数打包在一个单元中。然后这些单元就可为其他开发人员所共享，并因此有了模块化编程这种说法 — 即，从模块中构建程序。Linux 支持两种类型的库，每一种库都有各自的优缺点。静态库包含在编译时静态绑定到一个程序的函数。动态库则不同，它是在加载应用程序时被加载的，而且它...

程序员笔试题----链表的stable_partition_wutao02的博客-程序员宝宝

最近腾讯笔试了一道关于链表partition的题，要求稳定性，当时没有做出来。现在思考了一下，其实不难。只需要根据partition要求分别建立两个链表，然后遍历原链表，调整每个节点的链接即可。时间复杂度为O(n)空间复杂度为O(1)