P4045 [JSOI2009]密码

    • 80通过
    • 332提交
  • 题目提供者 njH2Q
  • 评测方式 云端评测
  • 标签 AC自动机 字符串 状态压缩,状压 各省省选 2009 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    众所周知,密码在信息领域起到了不可估量的作用。对于普通的登陆口令以,唯一的破解方法就是暴力破解——逐个尝试所有可能的字母组合,但这是一项很耗时又容易被发现的工作。所以,为了获取对方的登陆口令,在暴力破解密码之前,必须先做大量的准备工作。经过情报的搜集,现在得到了若干有用信息,形如:

               “我观察到,密码中含有字符串*。”

    例如,对于一个10位的密码以及观察到的字符串hello与world,可能的密码组合为helloworld与worldhello;而对于6位的密码以及到的字符串good与day,可能的密码组合为gooday。

    有了这些信息,就能够大大地减少尝试的次数了。请编一个程序,计算所有密码组合的可能。密码中仅可能包含a-z之间的小写字母。

    输入输出格式

    输入格式:

    输入数据首先输入两个整数L,N,分别表示密码的长度与观察到子串的个数。

    接下来N行,每行若干个字符,描述了每个观察到的字符串。

    输出格式:

    输出数据第一行为一个整数,代表了满足所有观察条件字符串的总数。

    若这个数字小于等于42,则按字典顺序输出所有密码的可能情况,每行一个,否则,只输出满足所有观察条件字符串的总数即可。

    输入输出样例

    输入样例#1: 复制
    10 2
    hello
    world
    输出样例#1: 复制
    2
    helloworld
    worldhello

    说明

    对于100%的数据,1<=L<=25,1<=N<=10,每个观察到的字符串长不超过10,并且保证输出结果小于2^63。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。