← 返回题目列表

AtCoder · abc032_b

B. 高桥君和密码

中文机器翻译题面 查看原题

問題文

高桥的公司有一个秘密保险箱。这个保险箱有密码,但高桥忘记了密码。 不过,幸运的是,我有一个密码提示,如下所示:

  • 密码是写在这张纸上的字符串。 s 长度 k 的任何子字符串 (*)。

高桥可以通过尝试所有可能的密码来打开保险箱!我很高兴。 但字符串 s 可能很长,并且字符串可能包含多个相同的子字符串。 s 也可能存在。显然,没有必要反复尝试重复的密码。 因此,我决定在手动尝试所有密码之前计算需要尝试多少个不同的密码。

你的工作是创建一个字符串 给定 s 的内容,任务是告诉高桥他需要尝试多少个不同的密码。

(※)文字列 s 的“子字符串”是一个字符串 从 s 中包含的某个区间中提取的字符串。 例如, 作为abc 的子字符串 示例包括 a,b,c,ab,bc,abc 。 ac 呀 请注意,类似 ba 的内容不是子字符串。


入力

输入是按以下格式从标准输入给出的。

s
k
  • 1 提示纸上写的字符串是 s (1≦|s|≦300) 。s 是一个小写字母 ( 仅a-z)。|s| 是一个字符串 表示 s 的长度。
  • 2 行包含一个可用作密码的整数。 可能大于 k (1≦k≦300) 。 k 是 |s| 。

出力

输出应按以下格式执行到标准输出。 在

1 行上,输出可能的密码字符串的数量。不要忘记最后的换行符。


入力例1

abcabc
2

出力例1

3

可用作密码的子字符串集合是 {ab,bc,ca}。


入力例2

aaaaa
1

出力例2

1

密码的可能子字符串是: 仅a 。


入力例3

hello
10

出力例3

0