#P4045. [JSOI2009] 密码

    ID: 2977 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>字符串2009各省省选江苏状态压缩状压AC 自动机

[JSOI2009] 密码

题目描述

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

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

例如,对于一个 1010 位的密码以及观察到的字符串 helloworld,可能的密码组合为 helloworldworldhello;而对于 66 位的密码以及到的字符串 goodday,可能的密码组合为 gooday

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

输入格式

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

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

输出格式

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

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

10 2
hello
world
2
helloworld
worldhello

提示

对于 100%100\% 的数据,1L25,1N101\leq L\leq 25,1\leq N\leq 10,每个观察到的字符串长不超过 1010,并且保证输出结果小于 2632^{63}